Czym różni się procesor zaprojektowany wyłącznie do programowania funkcjonalnego?


14

Procesory są w pewnym stopniu zaprojektowane z myślą o oprogramowaniu, które ludzie będą dla niego pisać, w sposób dorozumiany lub jawny.

Wydaje mi się, że jeśli spojrzysz na projekt architektury zestawów instrukcji, są one bardzo „imperatywne”, w tym sensie, że każda instrukcja koduje polecenie stylu imperatywnego. Wydaje mi się również, że obecne architektury zestawu instrukcji ewoluowały częściowo w zależności od rodzaju kodu tworzonego przez programistów.

Gdyby zaprojektować procesor od zera, wiedząc, że będzie on zawsze uruchamiał programy napisane w funkcjonalnym stylu programowania, to w jaki sposób procesor ten zostałby zaprojektowany inaczej niż istniejące procesory?


9
John Backus w swoim „Czy programowanie może zostać wyzwolone ze stylu von Neumanna?” wspomina o kilku takich pracach (sekcja 15).
Dmitri Urbanowicz,

Poszukaj maszyn do redukcji (wykresu) lub odwiedź lokalną bibliotekę badawczą z nadzieją, aby znaleźć egzemplarz wyczerpanej książki W. Kluge The Organisation of Reduction, Data Flow and Control Flow Systems (MIT Press, 1992).
Kai

2
Również książka Koopmana An Architecture for Combinator Graph Reduction (AP, 1990). Warto również spojrzeć na maszyny Lisp. en.wikipedia.org/wiki/Lisp_machine
Pseudonim

Myślę, że zasadniczo nasze maszyny będą zawsze konieczne, gdy będą działać z czasem, mutując ich stan.
orlp

Kilka przydatnych funkcji procesora to natywna obsługa thunks i bardziej wydajne skakanie. Również procesor może być w stanie przyjąć kilka skrótów, wiedząc, że niektóre lokalizacje w pamięci nie zostaną nadpisane w pewnym zakresie i procesor nie będzie musiał utrzymywać stosu w taki sam sposób, jak w językach opartych na stosach.
Przywróć Monikę

Odpowiedzi:


3

W rzeczywistości zostało to zrobione: https://en.wikipedia.org/wiki/Lisp_machine

Jednym z aspektów projektowania procesora dla FP jest wyrzucanie elementów bezużytecznych. GC jest bardzo ważny dla języków funkcjonalnych. Typowe implementacje wymagają, aby GC mógł rozróżniać dane wskaźników i dane niebędące wskaźnikami. W efekcie oznacza to przechowywanie dodatkowego fragmentu danych. Z tego powodu na przykład liczby całkowite OCaml mają tylko 31 bitów na architekturach 32-bitowych i 63-bitowe na architekturach 64-bitowych. Arytmetyka liczb całkowitych wiąże się z niewygodnymi dodatkowymi operacjami zmiany biegów. Inne języki (lub inne typy danych OCaml) mogą marnować całe słowa maszynowe dla tego dodatkowego bitu, tym samym używając 128 bitów dla 64-bitowych liczb całkowitych. Procesor natywnie zaprojektowany w kierunku GC może mieć 65-bitową szynę danych, ale 64-bitową arytmetykę.

To powiedziawszy, wiele niefunkcjonalnych języków również ma funkcje wyrzucania elementów bezużytecznych, a zatem skorzystałoby z odpowiednich architektur.

Inną rzeczą, która przychodzi na myśl, jest to, że użycie pamięci FP jest zwykle znacznie bardziej rozproszone niż w programach imperatywnych. Głównie dlatego, że używanie tablic jest mniej naturalne. W rezultacie programy te czerpią mniejsze korzyści z buforowania ciągłych fragmentów pamięci. Dlatego procesor FP może korzystać z różnych strategii buforowania.


1

Nie zmieniłby niczego lub wykorzystałby ogromne ustawienie równoległe jak w Reduceron i jego następcy PilGRIM 1 z ogromnym stosem.

Stwierdzenie, że nic by się nie zmieniło, na początku wydaje się odważne, ale ponieważ procesor jest sekwencyjny, istnieje proces tłumaczenia (kompilacja), który wykorzystuje dostępny sprzęt w celu zwiększenia wydajności. Gdyby istniała inna architektura, niektóre operacje byłyby szybsze, niektóre wymagałyby sztuczek hakerskich, aby je przyspieszyć.

Architektura, która zrobiłaby różnicę, wymagałaby szybszego działania mapy i list (nie cała historia, ale wystarczy pokazać efekt). Nie ma możliwości tworzenia dynamicznie zmieniającego się sprzętu do natywnego uruchamiania list, więc są one przechowywane w pamięci ciągłej. Trzymamy się tablicowej reprezentacji jakiejś formy. Aby uruchomić mapę w trybie niesekwencyjnym - wracamy do Reduceron. Tak skutecznie jedno centralne przetwarzanie kolejnych instrukcji i obsługa przetwarzania równoległego.

Co może się różnić, to możliwość załadowania wielu funkcji i uruchomienia ich bez żonglowania ramkami - ale dodanie wielu jednostek dla funkcji spowodowałoby bałagan z dostępem do pamięci.

Dodając do odpowiedzi kolana, GC byłoby korzystne, gdyby działało jako koprocesor, byłaby to bardzo fajna funkcja.

1: PilGRIM jest poprawnie opisany w Boeijink A., Hölzenspies PKF, Kuper J. (2011) Przedstawiamy PilGRIM: procesor do wykonywania leniwych języków funkcjonalnych. W: Hage J., Morazán MT (red.) Wdrażanie i stosowanie języków funkcjonalnych. IFL 2010. Notatki z wykładów z informatyki, tom 6647. Springer, Berlin, Heidelberg .


„Nie ma możliwości, aby rekursja była natywna”. Czy możesz wyjaśnić, dlaczego tak jest? Z początku wydaje mi się to zaskakujące.
user56834

Ponadto, czy redukeron jest czymś, co może być twardym procesorem, zamiast uruchamiać na FPGA?
user56834

Mój zło, miałem na myśli rodzimą rekurencję , ale jest to prawdopodobnie nieistotne. Muszę trochę poprawić.
Zły

0

Najpierw żart: ponieważ uruchamianie w 100% funkcjonalnego programu nigdy nie jest w stanie zrobić nic pożytecznego, wystarczy mieć tylko instrukcję NOP. (Otwieram to na wojny z ogniem).

Potrzebne będą więc instrukcje imperatywne dla IO i zwykłe wsparcie dla programowania imperatywnego.

W przeciwnym razie zależy to częściowo od faktycznego użytego języka. Dwójka moich myśli to Haskell i Erlang.

Wierzę, że Haskell mógłby skorzystać ze wsparcia dla list i map. Lista może być obsługiwana przez określone mapowania pamięci sprzętowej, zmieniając połączoną listę w kolejny zestaw adresów. Pierwszy element może znajdować się na adresie n, drugi na adresie n + 1 i tak dalej. Aby usunąć pierwszy element z listy, wystarczy zmienić wskaźnik n. Wreszcie po usunięciu wskaźnika n cała pamięć może zostać zwolniona. Mapy mogą być obsługiwane jako tablice asocjacyjne - wprowadź wartość wyszukiwania, a system pamięci zwróci element. Nie ma potrzeby wyszukiwania iteracyjnego.

Z kolei Erlang mógłby skorzystać ze wsparcia komunikatów / procesów i rekurencji ogona z pełnym stanem. Komunikaty i procesy mogą być obsługiwane na różne sposoby, jednym z przykładów może być bardzo duża liczba rdzeni przetwarzających. Rekurencję ogona można poprawić dzięki kontrolerowi pamięci, który pozwala na szybsze kopiowanie stanu, być może nie kopiując dużych fragmentów danych, ale po prostu modyfikując wskaźniki systemu pamięci.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.