Wskazówki dotyczące przechowywania w języku golfowym

Piszę język golfa.

Czy proponujecie zmienne, stos (y), taśmy, rejestry itp. Do przechowywania w języku golfowym? Co z niejawnym wkładem?

Szorstkie definicje:

• Zmienna jest po prostu nazwa (zwykle jeden znak długo w językach golfa), że wartość może być przypisany do, a później pobierane przez tą nazwą.
• Rejestr jest jak zmienna, ale ma swój własny (zwykle jeden bajt) Polecenia do ustawiania / uzyskiwania wartości.
• Stos jest zmienną długość tablicy / lista wartości, w którym ostatnio dodanego wartości (wartości „na górze”) są te, które są zmieniane.
• Kolejka jest jak stos, z wyjątkiem wartości „na dole ” są te, które są modyfikowane.
• ZA Taśma jest statycznym tablica / lista wartości, gdzie każda wartość ma współczynnik. Główną różnicą między stosem a taśmą jest to, że wartości na taśmie są modyfikowane na miejscu.

Byłbym wdzięczny za poznanie zalet i wad każdej opcji dla różnych scenariuszy i ogólnie. Unikaj opinii i kopii zapasowych uzasadnień.

Wszystkie typy przechowywania obejmują przechowywanie czegoś w jednym punkcie i pobieranie go później. Aby to zrobić tylko w jednej operacji, należy albo automatycznie zapisać lub pobrać, a w drugiej operacji określić pozycję przechowywanej wartości.

Oznacza to, że w przypadku jawnego przechowywania można utworzyć operator, aby pobrać n-tą obliczoną wartość przed tą operacją lub przywrócić bieżącą wartość po n operacjach. Alternatywnie, możesz użyć pozycji bezwzględnej od początku programu lub zrobić więcej rzeczy, takich jak automatyczne usuwanie niektórych elementów po niektórych operacjach (np. Na stosie). Można również utworzyć wielu operatorów, pobierających z różnych kopii magazynu z tymi automatycznymi operacjami lub bez nich. I powinieneś postarać się, aby maksymalna liczba potrzebna do określenia w operacjach była stosunkowo niewielka, abyś mógł przypisać jednego operatora do każdej liczby.

Ale w większości przypadków nawet nie potrzebujesz operatora, a język zrobi to domyślnie. Wtedy trzeba rozważyć bardziej znormalizowany model, taki jak stosy lub kolejki. Najbardziej udanym na razie wydawało się milczące programowanie, w którym nawet nie wspomina się bezpośrednio o pamięci.

Jeśli chcesz zaprojektować nowy taki model, możesz spróbować rozszerzyć oceny jako dag i spróbować pomyśleć o domyślnym dag, jeśli nic innego nie zostanie określone. Najprawdopodobniej domyślnie jest to tylko drzewo, z tym wyjątkiem, że wiele liści może być połączonych z tym samym wejściem. Możesz na przykład użyć kolejki dla zrównoważonego drzewa lub stosu dla głębokiego drzewa, gdzie liście są w większości stałe, lub czegoś w rodzaju Galaretki dla głębokiego drzewa, gdzie liście są w większości kopiami danych wejściowych.

Należy jednak pamiętać, że można zakodować kształt drzewa binarnego za pomocą tylko 2 bitów na operatora. Tak więc, jeśli twój język ma mniej niż 64 operatorów, możesz faktycznie zignorować tradycyjne modele i po prostu zakodować całe drzewo w wolnych bitach (nazwij je flagami replace_parent i below_leaf). Nawet jeśli jest więcej operatorów, możesz zrobić dość dobry domyślny (na przykład model Jelly) i 3 modyfikatory, aby go zmienić.

Możesz użyć tego samego modelu do ukrytego i jawnego przechowywania dla wygody, ale nie musisz. Na przykład możesz użyć stosu do przechowywania niejawnego, ale nie wyskakuj elementów w magazynie jawnym (lub w innym jawnym magazynie oprócz ukrytego). Prawdopodobnie nie będzie nazywany stosem w ostatecznej dokumentacji, ale masz pomysł.

Dla porównania, rozmiar idealnego kodowania drzewa binarnego to logarytm liczb katalońskich . Rozmiar idealnego kodowania „dwójkowego” dag jest logarytmem A082161 , ale oczywiście niepraktycznym. Zakłada się, że operator z inną kolejnością argumentów ma dwa różne operatory, dodając kolejny bit, gdy tak nie jest.

Czasami nadal możesz chcieć zmiennych dla pętli. Może być możliwe przepisanie pętli na inne sposoby. Ale jeśli naprawdę tego potrzebujesz, nie używaj 1-bajtowej konstrukcji oprócz nazwy w celu zdefiniowania zmiennej. chyba że używasz tylko wstępnie zainicjowanych wartości, zwykle bardziej efektywne jest użycie 1-bitowej flagi do określenia, czy odczytujesz, czy zapisujesz tę zmienną.

Sugeruję je wszystkie!

Co więcej, wszystkie przydają się czasem, a im więcej, tym lepiej! Domniemane dane wejściowe nigdy nie są złe , wystarczy mieć flagę, aby je wyłączyć. Zmienne są pomocne, więc nie trzeba ich znajdować na stosie lub taśmie; to samo z rejestrami. Stosy są pomocne do przechowywania danych, podobnie jak taśmy. Polecam próbę implementacji wielu, powiedzmy stosu i rejestrów, lub stosu i zmiennych, takich jak GolfScript. Jeśli potrafisz uczynić każdą funkcję jednym bajtem, wtedy twój język będzie prawdopodobnie skuteczny w grze w golfa, ponieważ możesz skorzystać z zalet każdej z nich.

Przykład:

• Powiedzmy, że chcę wziąć dwie liczby jako dane wejściowe i dodać ich długości ciągu
• Zmienne mogą być do tego lepsze (stos może nie)

• Przykładowy kod w GolfScript (z niejawnym wejściem):

  ~,\,+
  ~ # Eval input (e.g. "1 2" > 1, 2)
  , # Take Length
  \ # Reverse items on the stack
  , # Take Length
  + # Add
    # Implicit output
  

  Jednak w przypadku zmiennych (wiem, że jest dłuższy, po prostu nie musi zamieniać miejsc na stosie):

  ~,:a;,:b;ab+
  ~ # Eval input
  , # Get length
  :a# Store in "a"
  ; # Discard value left on stack
  , # Length
  :b# Store in "b"
  ; # Discard
  a # Recall a
  b # Recall b
  + # Add
    # Implicit output
  

Przeciążenia

Kolejną rzeczą, która może być pomocna, są przeciążenia. Na przykład, jeśli masz zmienną funkcję przechowywania, być może mogłaby być użyta jako monada (funkcja jednego wejścia; nie jestem pewien terminu poza J / K / APL), aby dodać do stosu lub taśmy.

Przykład:

c12 # Stores "1" into register 2
c1] # Pushes "1" onto the stack ("]" is used to denote the end of the monad)

Sugerowałbym posiadanie pewnej szybko użytecznej pamięci (z podanej - taśmy, kolejki, stosu) i pewnej stałej pamięci (zmienne, rejestry), aby rzeczy nie przeszkadzały, gdy program robi coś niezwiązanego. Powiedziałbym, że znacznie więcej rzadko daje cokolwiek i pozostawia więcej znaków wolnych dla więcej instrukcji 1-bajtowych.

Z podanych definicji, te, które moim zdaniem działałyby najlepiej, to stos i rejestry.
Stos, ponieważ taśma musi używać funkcji tylko do przechowywania nowej rzeczy, podczas gdy stos powinien mieć proste funkcje push i pop (zwykle wbudowane w polecenia). Rejestry, ponieważ zajmują mniej bajtów zwykle w porównaniu do zmiennych, a jeśli potrzebujesz czegoś więcej niż 2-4 różnych rzeczy, robisz coś źle.

Nie ograniczaj ich funkcji tylko do tego, co sugerują ich nazwy lub definicje - niektóre funkcje na put the 1st thing of the stack on top of the stackpewno mogą pomóc.

Zasadniczo istnieją dwa rodzaje pamięci, które należy traktować inaczej; dostęp do ostatnio wygenerowanych wartości i / lub danych wejściowych; i długoterminowe przechowywanie.

W przypadku przechowywania długoterminowego zmienne wydają się działać najlepiej; wszystko z ograniczoną liczbą opcji nie jest skalowane (chociaż języki z tą właściwością, takie jak Jelly, mogą jednak dość dobrze sobie radzić nawet przy średnich zadaniach). Jednak podczas przechowywania zmiennej nie ma potrzeby podawania nazw zmiennych; po prostu mam polecenie do przechowywania wartości w zmiennej i automatycznego generowania nazw według przewidywalnego wzorca, tak aby przechowywanie i wyszukiwanie wartości mogło być jednym poleceniem w prostych przypadkach. (Na przykład możesz mieć komendy do przywracania ostatnio przypisanej zmiennej, drugiej ostatnio, trzeciej najnowszej itd., Do małej stałej liczby oraz ogólnej komendy, która wzięła argument.)

W przypadku przechowywania krótkoterminowego chcesz mieć jak najwięcej domniemania. Prawie wszystkie języki gry w golfa domyślnie łączą wyjście jednego polecenia z wejściem następnego; dokładny sposób, w jaki to się dzieje, różni się w zależności od języka, ale zwykle dochodzi do tego samego. Jednak drugie wejście dla polecenia 2-wejściowego jest bardziej interesujące. Pobieranie ze stosu działa dobrze w przypadkach, w których wartości są używane tylko raz, ale nie skalują się dobrze przy ponownym użyciu wartości. (Staraj się unikać prymitywów manipulacji na stosie; jeśli musisz skorzystać z nich, marnujesz dużo bajtów.) Alternatywnie, używając danych wejściowych użytkownika lub ostatnio przypisanej zmiennej jako domyślnego drugiego argumentu, można zaoszczędzić kilka bajtów na proste programy, chociaż ty

W języku golfowym, nad którym obecnie pracuję, używam kombinacji bardzo taniego mechanizmu (pojedynczego bitu ), aby określić kształt drzewa parsowania, domyślnie automatycznie uzupełniając brakujące argumenty z danych wejściowych użytkownika i punkt kontrolny podejście, które umożliwia ustawienie domyślnych brakujących argumentów na coś innego (plus wiele specjalnych przypadków). W pewnym momencie prawdopodobnie dodam zmienne, aby przekazywać informacje na większe odległości w programie.

Sugeruję taśmę i rejestr.

Wolę taśmy od stosów, ponieważ taśmy mają zwykle mniej elementów, co ułatwia manipulowanie nimi. Ponadto możliwość umieszczania elementów na taśmie w rejestrze i odwrotnie zapewnia łatwy, krótki kod.