Старые реализации бейсика

Как хранятся строки в старых бейсиках? Они же нумерованые все, и например, при последовательном вводе строк 10, 20 и последующем вводе строки 15, должно произойти нечто не тривиальное, что не привело бы к тотальному копированию кусков памяти. Что?

Я бы делал связанный список с дополнительными указателями на сотни или тысячи.

Как они получались такими маленькими и быстрым?

Вряд ли они были быстрыми. Быструю графику на Z80 на бейсике не получалось делать.

Какие структуры данных использовались?

Те же, что и сейчас?

Как хранятся строки в старых бейсиках?

Список?

Как они получались такими маленькими и быстрым?

Так они и не умели ничерта. А быстрыми... это вряд ли.

А есть какая-нибудь спека на эти басики? У меня валялся где-то ман по спектрумовскому басику, но благополучно канул в лету.

Связанный список, да, хорошая идея, но что значит доп. указатель на сотни и тысячи?

Ну, про быстроту я не так выразился. Я вообще удивлен, что тогда были интерпретируемые языки.

bourne shell в 77-м году была написана, чего удивительного :) Хотя машины конечно несопоставимы. 8-битные системы были просто игрушками.

но что значит доп. указатель на сотни и тысячи

Ну вот надо тебе на строку 1150 перейти. Для этого придётся пройти список от начала. А можно держать указатель на 1100-ую строку (или первую строку с номером >= 1100). Тогда переход можно сделать быстрее. Сами указатели можно в таком же списке держать.

В википедии есть что почитать, как ни странно.

http://en.wikipedia.org/wiki/Commodore_BASIC

Как они такими маленькими получались?

SmallBASIC с исходниками.

Подробности в книжке «С» (PDF):
7.20. Интерпретатор языка SmallBASIC
7.39. Полный файл интерпретатора.

Ну, это не совсем то. Но все равно спасибо.

рекомендую посмотреть qb64

Как хранятся строки в старых бейсиках?

Из журнала Радио №3 1986 г. (внизу): На рис.4 показан формат строки программы на Бейсике в том виде, в каком она хранится в памяти микро-ЭВМ. В начале каждой строки два байта отведены для хранения указателя адреса начала следующей строки программы, следующие два байта хранят номер строки, а заканчивается она байтом, заполненным одними нулями. Таким образом, текст программы хранится в памяти в виде специальной структуры данных. называемой в литературе «односвязным списком».

О, спасибо! В принципе, после того, как мы заговорили про списки, я к такому виду и пришел.

Хотя i-rinat тоже предлинтересную идею, но более сложнуую.

В википедии есть что почитать, как ни странно.

http://en.wikipedia.org/wiki/Commodore_BASIC

+1. Верно :)

The order of execution of Commodore BASIC lines was not determined by line numbering; instead, it followed the order in which the lines were linked in memory.[3] Program lines were stored in memory as a singly linked list with a line number, a pointer, and then the tokenized code for the line. The pointer contained the address in memory of the next program line. While a program was being entered, BASIC would constantly reorder program lines in memory so that the line numbers and pointers were all in ascending order. However after a program was entered, manually altering the line numbers and pointers with the POKE commands could allow for out-of-order execution or even give each line the same line number. In the early days, when software written in BASIC was available commercially, this was a software protection technique used to discourage casual modification of the program.

http://zxpress.ru/book_articles.php?id=1387

Там про спектрум написано. Правда я там не нашёл о том, что было когда вставляли строку №15. Но если учесть, что строки хранились последовательно, то да - перемещали куски памяти туда сюда при вставке/удалении строк.

Не, ну с 15 строкой вроде понятно. Там то два указателя поменяь. А вот алгоритм поиска «куда вчставить» я бы почитал.

Смотришь на номер и длину строки. Если номер меньше вставляемой, переходишь на длину строки вперёдь, иначе передвигаешь всё аж до конца програмы на длину вставляемой строки и образовавшийся пропуск вставляешь новую строку.

Там то два указателя поменяь

Ты не понял, кмк. Строки програмы последовательно хранились. Это как бы не односвязный список, а последовательный набор записей с закодированной длиной записи в 3 и 4 байтах записи. Как-то так. Всмысле таблицы из указателей на строки не было. Известен был только адрес первой строки (или 10ой там).

Кстати в спектруме48 ещё был такой трюк заимплементирован: операторы кодировались одним байтом. Этот байт был сразу после длины строки, емнип. Парсеру не надо было определять что за оператор, а просто делался call по адресу из таблицы в пзу.

Епт, афигеть, это же медленно... С другой стороны - мы то это во время ввода программы делаем, а не выполнения, так что не так критично, как мне на первыйвзгляд показалось.

Может просто хранить список указателей настроки программы? В нем перестановок меньше прийдется делать. Или мбыть может двусвязный список замутить?

Вообще, двусвязный список вроде удобный вариант. Но кодить его на асме лень, если честно.

Кстати, про оптимизацию в спектруме. Там все операторы были именно в начале строки? И все они одинаково легко определялись?

Одним байтом - точно. А вот с начала ли строки - не помню. Отлично помню, что после ввода номера строки и пробела курсор сразу переходил в режим [К], а это операторы были (если ты спектрум видел, то поймёшь о чём я, если нет то почитать можешь здесь).

upd: Он сразу с новой строки был в режиме [К] пока до оператора не дойдёт. Вот после оператора переходил в [L].

посмотри на реализацию внутреннего интерпретатора форта

для x86 17 байт.

для PDP11 - а его просто нет ибо наличие автоинкремента по произвольному регистру и индексирование перехода по «любому» регистру приводит к размазыванию nxt по коду.

т.е в некотором смысле вариант шитого кода вполне на pdp11 переоткрывался каждым пишущим на асме стремящимся сэкономить битики.

как ни странно в старых басяках структуры были самые базовае тот же FAT в msdos - это наследие бэйсиковского(ms) менеджера свободных «блоков».

ибо микропроцессор после калькулятора настолько быстр , что использование лобовых методов(линейный поиск) на тех обьёмах был «незаметен»

учитывая ренум там был просто список(одно/двухсвязный) где место вставки определялось номером и сквозным проходом для вставки , а сам ренум делался за 1 проход заменной номеров строк.

на том же спектруме был «байткод» после ввода строки в памяти фиксировались кода команд (да и сам метод ввода был выбором)- на этом экономили на уменьшении парсера.

Ну блин. В 21ом веке люди как-то умудряются писать код в текстовом редакторе, а потом скармливать его компилятору/интерпретатору.

Или ты repl для бейсика задумал сделать?

Помню как изучал хранение программы на Бейсике на моей Весте. Там все было по порядку (Т.е. вставка/изменение строки копировала весь хвост кода), но самое прикольное, что все названия команд занимали 1 байт. И я даже когда-то записывал соответствие кода-строке.

Списки слишком шикарно было. Тратить память на опустевшие куски кода никому не хотелось. (Не забывай что строки тоже менялись)

Ну понятно, значит будем решать в лоб.

Да, пишу repl. Ну, само собой, возможность загрузить текст программы целиком будет.

Спасибо, а что за менеджер свободных блоков? Типа аллкотора памяти или что?

Ну жошь, чо )). Запили туда ооп расширение и лямбда ф-и!

А лучше сделай виртуальную машину и для неё образ (типа пзу). Будет олдскульненько, но кроме тебя никому не нужно.

google fat (file allocation? table)

ну и вот http://altairbasic.org/index2.html

Угадал! Пишу для своей вм, RISC прдобная, со стеком. Аоифметика только регистр-регистр, переходы и операции с памятью по мимо регистров используют константные значения. Стек только для регистров.

Я не знаю почему, но мне нравятся такие велосипеды. Сюда же можно отнести и компилятор недо-сишки (лол, под другую вм), и ассемблеры для этих вм.

Короче, ни кому не нужно, но для меня писать прожки под свой «компьютер» используя свои инструменты это лютое удовольствие.

Я даже намереваюсь придумать историю для своего будущего софта и железа, все выдумать. А если еще и игру запилить, типа 0х10с, только сами знаете с кем и чем, то... Кажется я чуть-чуть повернут.

А, блин, затупил. Прошу прощенья.

Ах да, компилятор недо-сишки я писал два года, начал в 16 лет. На конструкторе игр.

но самое прикольное, что все названия команд занимали 1 байт

Это на большинстве систем так было. Даже на МК-85 (а куда деваться, когда всей оперативки, включая системную и переменные — 2кБайт).

…

Кстати, напомню ещё, что вставка строки обычно по времени была быстрой (условно мгновенной) на большинстве реализаций. А вот оператор RENUM — часто очень медленный. Вот по нему, видимо, физическая реаллокация строк и происходила. Копирование в памяти в те времена тоже очень медленным было.

qbasic
ms-dos 5

Я не знаю почему, но мне нравятся такие велосипеды

Думаю таким многие страдали. И я в том числе.

Кстати, напомню ещё, что вставка строки обычно по времени была быстрой (условно мгновенной) на большинстве реализаций.

http://ru.wikipedia.org/wiki/ПК8000

Оперативная память 48 КБ
Тактовая частота CPU 1,78 МГц

Как бы сдвинуть один раз кусок памяти не должно занимать много времени

Как бы сдвинуть один раз кусок памяти не должно занимать много времени

В компах «8080» для копирования/перемещения кусков памяти вместо процессора Intel 8080А (K580ВМ80А) использовался контроллер ПДП Intel 8257 (К580ВТ57), который работал существенно быстрее.