Journey of Science

Zapraszam wszystkich zainteresowanych nauką na mój nowy blog popularnonaukowy. Znajdziecie tam ciekawe wpisy z różnych wykładów w których brałem udział. Tematyka notek jest szeroka: od socjologii ("Dlaczego talerze nie mogą być kwadratowe?") do nauk ścisłych ("Wycieczka do reaktora Maria"). Mam nadzieję, że wam się spodoba.

http://journeyofscience.tumblr.com/

Pułapka

Pisałem ostatnio program wykonujący dość długo skomplikowane obliczenia. Przy pewnych danych wejściowych program przepełniał stos i się wysypywał. Po kilku godzinach frustracji postanowiłem przepisać każdą funkcję na wersję ogonową.
W trakcie tego jak to robiłem zacząłem się zastanawiać nad programowaniem funkcyjnym. Generalnie to jego główną ideą jest to, że piszemy w nim nie jak coś policzyć (tak jak to jest w programowaniu imperatywnym) tylko czym wynik danej funkcji ma być. I to jest bardzo przyjemne i bardzo fajnie się tak pisze - wszystkie funkcje wklepuje się niemal intuicyjnie. Problem jest jak dojdzie do funkcji ogonowych. Funkcje ogonowe (zwłaszcza nieco bardziej skomplikowanych obliczeń) są w ogóle nie intuicyjne. Trzeba zacząć się zastanawiać co ma być akumulatorem (może trzeba dać dwa akumulatory?) jakie dodatkowe informacje należy przekazać itp. itd.
Na szczęście udało mi się wszystkie funkcje przepisać na wersje ogonowe (Teraz jak ktoś spojrzy na kod to już się nie dowie co to a to robi :) ). Nie udało się przepisać tylko jednej. Może ktoś z was będzie miał pomysł. Funkcja dostaje długość listy l oraz sumę s i generuje wszystkie listy o długości l zawierające liczby dodatnie sumujące się co najwyżej do s. Na przykład: funkcja 3 5 = [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,3,1][2,1,1],[2,1,2],[2,2,1],[3,1,1]]. Kolejność list nie jest ważna.
Gdy już miałem prawie wszystkie funkcje ogonowe i sprawdziłem ręcznie, że program nie wywiesza się na tej funkcji nie ogonowej... program dalej się wywieszał :-) Zasięgnąłem zatem opinii dokumentacji i okazało się... że standardowa funkcja map nie jest ogonowa... Troszeczkę się zdenerwowałem. Gdzie kolejność elementów nie była dla mnie ważna użyłem funkcji rev_map. W innych sytuacjach napisałem własną funkcję map:

let mymap l p = rev (map l p);;

Program wciąż nie działa - typ razem już na mojej funkcji (opisanej wyżej). Przepisałem program do C++ działa i to sto razy szybciej ;)

Labirynt cz II

Normalnie bym nie pisał - bo sesja, ale udało mi się odratować kod źródłowy słynnego już labiryntu. Oto i on:

Rysuj
  | form pen ile i |
  form := Display.
  pen := Pen newOnForm: form.
  pen up.
  form fillWhite.
 
  ile := lab size.
  i := 1.
  [i <= ile] whileTrue:
  [
    pen goto: (lab at: i).
    pen down.
    pen goto: (lab at: (i+1)).
    pen up.
    i := i + 2.
  ]

  pen goto: 0@0.
  pen down.
  pen goto: (10*xsize)@0.
  pen goto: (10*xsize)@(10*(ysize // 2)).
  pen goto: 0@(10*(ysize // 2)).
  pen goto: 0@0.
  pen up.

  pen goto: 0@(10*((ysize // 2) +1)).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1)).
  pen goto: (10*xsize)@(10*ysize).
  pen goto: 0@(10*ysize).
  pen goto: 0@(10*((ysize // 2) +1)).
  pen up.

  pen goto: 0@(10*((ysize // 2) +1) + 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1) + 1).
  pen up.

  pen goto: 0@(10*((ysize // 2)) - 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2)) - 1).
  pen up.

  [Sensor keyboardPressed] whileFalse: [].
  Display restore.

Stworz: x y: y
  | r v |
  xsize := x.
  ysize := y.
  r := Random new.
  lab := OrderedCollection new.
  0 to: (x-1) do:
    [:x1 |
      0 to: (y-1) do:
        [:y1 |
          (y1 = (y // 2)) ifFalse:
          [
            v := r nextInt: 5.
            (v > 2) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*(x1+1))@(10*y1) ].
            (v < 4) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*x1)@(10*(y1+1)) ].
          ].
        ].
    ].