Związany czas wykonywania obliczeń w haskell

Question

Piszę sztuczną grę w Haskell i chcę przeszukiwać drzewo stanu gry przez określony czas (tzn. Zawsze chcę, aby sztuczna inteligencja zajęła 3 sekundy, aby zrobić decyzja o tym, co należy zrobić)

Jak mogę to zrobić w czystym języku, takim jak Haskell? Spodziewam się, że będę musiał nurkować w wątkach i takich, ale wolałbym zminimalizować to tak bardzo, jak tylko mogę.

Answer 1

Jeden pomysł: Kombajny timeout (sugerowane przez @MathematicalOrchid) ze zmiennymi modyfikowalnych z SafeSemaphore do przechowywania wartości pośrednich każdym razem, gdy proces oblicza częściową wynik:

import Control.Monad 
import Control.Concurrent.MSampleVar 
import System.Timeout 

fac :: Integer -> Integer 
fac 0 = 1 
fac n = n * fac (n - 1) 

tmo :: Int -> ((a -> IO()) -> IO()) -> IO (Maybe a) 
tmo ms f = do 
    mvar <- newSV Nothing 
    timeout ms (f (writeSV mvar . (Just $!))) 
    readSV mvar 

longComp :: (Integer -> IO()) -> IO() 
longComp save = let loop n = save (fac n) >> loop (n + 1) 
       in loop 0 

main :: IO() 
main = tmo 10000 longComp >>= print 

Funkcja przekazane tmo pobiera jako pierwszy argument akcja, której może użyć do zapisania wyników pośrednich. Jeśli zostanie przekroczony limit czasu, zwrócony zostanie ostatni zapisany wynik. Wynik jest konwertowany na wartość WHNF, tak aby rzeczywiste obliczenia odbywały się w wątku, który zapisuje wynik, a nie w tym, który przetwarza go po powrocie z tmo.

W tym wariancie funkcja przekazana do tmo musi zapisać wynik, ale nie może go zwrócić. Ale byłoby łatwo zmodyfikować tak, aby jego podpis był (a -> IO()) -> IO a.

Jeśli chcesz zachować czystość, proponuję stworzyć własną monadę, która otoczy ten pomysł, nie pozwalając na to, by IO się skończył.

---

Aktualizacja: zauważyć, że:

Nie ma gwarancji, że wyjątek zostanie dostarczony natychmiast, chociaż runtime będzie dążyć do zapewnienia, że ​​arbitralne opóźnienia nie występują.W GHC wyjątek można podnieść tylko wtedy, gdy wątek osiągnie bezpieczny punkt, , gdzie bezpiecznym punktem jest miejsce przydzielania pamięci. Niektóre pętle nie wykonują żadnej alokacji pamięci wewnątrz pętli, a zatem nie mogą być przerywane za pomocą polecenia throwTo.

(z dokumentacji throwTo). W powyższym przykładzie fac nie przydziela żadnej pamięci, więc dla dużych liczb nie zostanie natychmiast przerwana.

Aktualizacja: stworzyłem małą bibliotekę na podstawie tych pomysłów, które definiuje monads obliczeń, które mogą powrócić częściowych wyników przed zwróceniem końcowy jednego lub umiera na timeout. Patrz: https://github.com/ppetr/timeout-with-results

Answer 2

Ponieważ wynik, którego szukasz zależy od czasu, nieuchronnie wiąże się to z nieczystym kodem.

Wygląda System.Timeout z pakietu base zapewnia zdolność do uruchamiania obliczeń I/O przez pewien czas (za komentarzu przez leftaroundabout.) Więc wszystko co musisz zrobić, to napisać IO obliczeń, która zwraca wynik you” Niemniej jednak ... trudnym zadaniem jest sprawienie, aby w wyniku działania IO obliczyć wynik, a nie tylko zwrócić nieoceniony wynik. W tym celu, trzeba, czego potrzebujesz evaluate od Control.Exception.

Answer 3

System.Timeout to droga. Ma bardzo przejrzysty interfejs, który wcale nie sprawia wrażenia, że ​​niszczysz wątki.

Przeszukiwanie przestrzeni gry brzmi jak czysta obliczeń i System.Timeout biegnie IO działania, więc trzeba owinąć wartość w return i ocenić kod tyle ściśle, że timeout nie od razu uwierzyć odpowiedzi został zwrócony jak tylko zostanie oceniony w WHNF.

Jest przykład here tego, jak kod może wyglądać, z podobnego problemu, który miałem.