Czy możliwe jest współbieżne używanie języka programowania opartego na stosie?

14

Czytałem o językach programowania opartych na stosie, takich jak FORTH i Cat , i wydaje się, że biorąc pod uwagę ich naturę, mogą one wykonywać tylko jedną akcję na raz, niezależnie od swojego paradygmatu (FORTH jest konieczny, a Cat funkcjonalny).

Język imperatywny zmodyfikowałby stos, a język czysto funkcjonalny, taki jak Joy , zwróciłby nowy stos, ale chodzi o to, że jednocześnie używany jest tylko jeden stos.

Czy zatem języki programowania oparte na stosie mogą być współbieżne? Czy mogą osiągnąć współbieżność, używając wielu stosów jednocześnie lub czegoś podobnego?

Czy jest możliwe wdrożenie leniwej oceny w języku programowania opartym na stosie?

Proszę mnie poprawić, jeśli coś źle rozumiem na temat języków i pojęć wymienionych powyżej

Armando H.
źródło
5
Jak jakikolwiek imperatywny język może być współbieżny?
Bergi,
Czy naprawdę masz na myśli współbieżność (która nie jest tak trudna do osiągnięcia, wystarczy użyć wielu wątków z niezależnymi stosami i pamięcią współdzieloną) lub równoległość?
Daniel Jour
@DanielJour, jeśli dobrze rozumiem, paralelizm oznacza jednoczesne wykonanie, podczas gdy współbieżność oznacza niezależne wykonanie, więc tak, mam na myśli współbieżność. Czy mógłbyś rozwinąć więcej informacji o niezależnych stosach dla każdego wątku?
Armando H.,

Odpowiedzi:

16

Czy zatem języki programowania oparte na stosie mogą być współbieżne?

Pewnie.

Czy mogą osiągnąć współbieżność, używając wielu stosów jednocześnie lub czegoś podobnego?

Już w przypadku normalnych języków wielowątkowość zwykle oznacza posiadanie wielu stosów „połączeń”. Byłoby całkowicie naturalne, aby każdy wątek miał własny stos danych. Na przykład byłoby łatwo mieć aktora, którego ciało zostało zaimplementowane przez kod w języku opartym na stosie. Wyraźna równoległość paradnotacji a GHC powinna być dość prosta. Główny problem z równoległym wykonywaniem rzeczy polega na tym, że nie wiesz, jaki będzie efekt stosu kodu, dopóki go nie wykonasz. Jednak stosując składnię podobną do radości można sobie wyobrazić [a b c] parwykonywaniea b calbo na pustym stosie, albo na kopii stosu i utrzymując najwyższy element stosu po zakończeniu (lub przesuwając pewną wartość manekina, jeśli stos jest pusty). Możesz sobie wyobrazić wariacje. Implikowany paralelizm byłby trudniejszy do naiwnego działania w porównaniu, powiedzmy, z czysto funkcjonalnym językiem, ale z pewnością można by to zrobić. Skompilowany kod zdefiniowanego przez użytkownika kombinatora często nie różni się zbytnio od „normalnego” kodu.

Czy jest możliwe wdrożenie leniwej oceny w języku programowania opartym na stosie?

Nieznane efekty stosu są znów trudną częścią. Jeśli zaprojektujesz język tak, aby wszystkie efekty stosu można było ustalić statycznie, nie będzie to zbyt trudne. Jeśli masz lenistwo, wyrażaj się wyraźnie, to również wydaje się stosunkowo proste i wyglądałoby mniej więcej tak, jak cytaty Joy i i. Jeden język, który nazywa się leniwym językiem konkatenacyjnym, wydaje się mieszać oba powyższe podejścia z tego, co mogę powiedzieć. Nie bardzo rozumiem, jak domyślnie leniwy język konkatenatywny działałby w obliczu dynamicznych efektów stosu, przynajmniej nie w jakikolwiek sposób użyteczny, ale może to być po prostu brak wyobraźni z mojej strony.

Nawiasem mówiąc, często języki oparte na stosie mają wiele stosów, np. Forth ma stos danych i stos zwrotny, na którym można również umieszczać dowolne dane.

Derek Elkins opuścił SE
źródło
8

Wiem trochę o FORTH, więc ograniczę się do tego. Jest to język niskiego poziomu, który zapewnia jako programista dostęp do wszystkich zasobów sprzętowych. Możesz więc robić, co chcesz.

Konkurencja

Aby mieć równoległe programy (edytuj: używane w przypadku prawdziwych programów współbieżnych) potrzebujesz co najmniej dwóch jednostek wykonawczych (CPU-ów). Zaimplementowanie słowa w FORTH byłoby raczej trywialne, mówiąc na przykład: „uruchom to słowo na procesorze 2, używając tych dwóch argumentów”. Słowo przydzieli dwa potrzebne stosy na procesorze 2 i zacznie je uruchamiać. Będziesz musiał nieco ograniczyć się dokładnie w tym, jakie konstrukcje możesz użyć w tym programie.

Jeśli liczba współbieżnych programów jest większa niż liczba jednostek wykonawczych, wybrałbyś programy „pseudo równoległe”. Zasadniczo istnieją dwa sposoby, aby to zrobić: coroutines lub zapobiegawcza wielozadaniowość. W każdym razie jest możliwe (niełatwe, ale dobrze opisane w literaturze), jak to osiągnąć, a FORTH umożliwia dostęp do wszystkich potrzebnych rzeczy na niskim poziomie.

Leniwa ocena

Oczywiście możesz to zrobić w FORTH, jak w prawie każdym języku programowania. Nie będzie tak elegancki ani „wbudowany”, jak na przykład Haskell. Podam bardzo naiwny przykład.

Chodzi o to, że definiujesz „funkcję” (tutaj używana luźno), która zwraca zestaw rzeczy. Przykładem może być funkcja zwracająca wszystkie liczby całkowite. Następnie wykonujesz operacje na tym zestawie, a po zakończeniu podaj wynik. Na przykład możesz zsumować wszystkie liczby całkowite, dopóki suma nie będzie większa niż 1000. Nie leniwa ocena najpierw przydzieli wszystkie liczby całkowite jako zbiór, co jest niemożliwe, ponieważ istnieje nieskończona liczba liczb całkowitych. Wtedy zacząłby działać na tym zestawie. Leniwa implementacja mogłaby „dać mi następną wartość w zestawie”. Aby to zrobić, potrzebna jest tylko jedna zmienna w funkcji „ostatnia wartość daje”.

Haskell robi to w ten sposób. Oczywiście obsługuje bardziej skomplikowane sytuacje, ale pomysł jest taki sam. Powoduje ocenę oceny w sposób, który pozwala programistom skoncentrować się na problemie, a nie na tym, jak go rozwiązać.

ghellquist
źródło
4
„Aby mieć prawdziwe współbieżne programy, potrzebujesz co najmniej dwóch jednostek wykonawczych”. To tylko kwestia implementacji. Z perspektywy języka programowania prawie nie ma różnicy między dwoma wątkami działającymi na jednym procesorze lub na dwóch. W pewnym sensie każdy wątek można traktować jako „jednostkę wykonawczą”.
Dyskretna jaszczurka
1
Czasami należy wziąć pod uwagę szczegóły dotyczące wdrożenia. Jednym z przykładów jest łączenie się ze światem rzeczywistym poza prawdziwym komputerem. W trudnym czasie rzeczywistym, zgodnie z „prawidłową odpowiedzią zbyt późno jest nieprawidłowa”, czas może być inny, gdy porównasz uruchamianie na dwóch jednostkach egzekucyjnych z działaniem zmieszanych na jednej jednostce.
ghellquist
Czasami robimy. Wątpię jednak, aby taki był przypadek. Na przykład pytanie nie wspomina o wymogach planowania w czasie rzeczywistym.
Dyskretna jaszczurka
3
„Współbieżność”! = „Równoległość”. Można powiedzieć, że wiele wątków działających na maszynie jednoprocesorowej działa równolegle ze sobą, nawet jeśli nie odbywa się przetwarzanie równoległe.
Solomon Slow
Punkt na temat współbieżności vs równoległości. Zmienię tekst.
ghellquist