Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
| | | | Shaos wrote: Решил для начала попробовать сделать интерпретатор гибрида Hope+Prolog на языке JavaScript - входными данными для интерпретатора будут не текст программы или байт-код, а некая иерархическая структура в виде родной для джава-скрипта JSON-нотации. На верхнем уровне это будет массив, состоящий из объектов, описывающих определения типов данных и функции языка Hope, которые внутри будут также представлять из себя иерархические структуры вложенных объектов. Возможная структура объекта: { "T":M, // где M - тип объекта "O":тело-объекта // может быть null, число, массив, объект } Возможные значения типа: 0 - nothing 1 - use (подключение модуля): массив строк 2 - library (список атомов, использованных в коде): массив строк 3 - data (определение нового типа данных): массив объектов 4 - call (вызов функции): массив объектов 5 - dec (определение функции): объект с полями A (число) и D (массив объектов) 6 - special (специальные команды): строка 7 - lambda (определение безымянной функции): массив из двух элементов 8 - if/then/else: массив из трёх элементов 9 - let/in и where (а также letrec и whererec): массив из трёх элементов 10 - type (тип): число - идентификатор атома 11 - cons (простой конструктор): идентификатор атома 12 - cons(...) (сложный конструктор): объект с полями A (число) и O (объект) 13 - tuple (набор элементов): массив объектов 14 - num (число): число 15 - char (буква): число - код символа ... | | | | |
Всё таки имя в каждом объекте наверное необходимо, а точнее идентификатор имени, т.е.
{
"t":M, // где M - тип объекта
"a":N, // где N - идентификатор имени объекта (может быть null там где неприменимо)
"o":тело-объекта // может быть null, число, массив, объект
}
|
20 Jan 2012 22:16 |
|
|
7400
Maniac
Joined: 14 Jul 2011 02:18 Posts: 254 Location: Гомель
|
а можно увидеть листинг средненькой программы?
хорошоб добавить новых типов например сверхдлинный тип интеджер аля 512 байт
|
22 Jan 2012 10:45 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 863
|
Shaos объединил эти два сообщения в одно и оставил тут, т.к. они достаточно правильно отражают мотивацию
У Hope и Prolog есть одна общая черта: вычисления производятся путём сопоставления с образцом и выполнения соответствующих этому сопоставлению действий. Однако, многие (может даже и все) реализации Prolog-а не используют lazy (отложенных) вычислений, которые есть в Hope, а в Hope нет возможности выполнять унификацию переменных при сопоставлении и выдачи нескольких результатов при успешном сопоставлении с одним образцом.
Да, забыл ещё сказать: в Prolog-е нельзя описывать функции. Там все арифметические вычисления производятся встроенным предикатом "is", и изменить его, с целью добавления подобной функциональности, никак нельзя.
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
23 Jan 2012 05:31 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
Листинг увидеть пока не получится, т.к. я ещё не определился с тем, как это всё должно сосуществовать вместе. По поводу интов неограниченной длины - да, можно сделать (как в CommonLisp) - но позже.
Ещё из идей - возможность хранения набора прологовских фактов в реляционной базе данных - например SQLite. Но это сильно потом - т.к. оно будет только на сервере (не в джаваскриптовом клиенте).
|
23 Jan 2012 16:09 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 863
|
Я бы ещё промежуточные результаты вычислений в базу засунул. Если мы не хотим вычислять два раза результат функции с определёнными аргументами, то это соответстивие "аргументы->результат" надо где-то хранить. Ладно, если их не больше сотни (тогда можно и в памяти некий кэш иметь), но когда некая рекурсивная функция вызывает себя мульён раз...
А если иметь ввиду, что промежуточный результат может быть не только значением, но и недовычесленным лямбда-выражением (из-за отложенных вычислений), то можно уже задуматься, как хранить в базе и такие результаты.
А если мы сможем хранить в базе выражения, то можно и факты, и правила, и функции - всё хранить в базе, а интерпретатор писать на SQL
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
24 Jan 2012 00:52 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
про хеши я уже размышлял в одном из функциональных топиков - тут есть свои плюсы и минусы - скорее всего нужны будут некие эвристики на тему что можно хранить, а что нет - иногда будет быстрее вычислить результат, чем ворочать ленивое выражение в памяти или базе данных
|
24 Jan 2012 06:32 |
|
|
7400
Maniac
Joined: 14 Jul 2011 02:18 Posts: 254 Location: Гомель
|
по моему не стоит хранить результаты в базе данных
т.к. веник довольно медленный и допустим для вычисления факториала большого числа нам придется по мульену раз считывать с веника числа да причем они в базе искаться будут в этоге все это время в озу лучше все пихайте благо меньше 2 гигов этого чуда уже редко где встретиш
(если в мобилки по гигу пихают)
|
24 Jan 2012 11:31 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
ну во-первых, во всех современных операционных системах есть такая штука как кеш - прямого побайтового доступа к файлам уже давно нет - всё кешируется и буферизируется, а во-вторых, тот же SQLite умеет работать с базами данных, хранимыми в оперативной памяти
|
24 Jan 2012 17:03 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 863
|
Shaos, тебе не кажется, что ленивые вычисления, которые очень помогли бы при организации ввода-вывода, не вписываются в концепцию логического языка?
Вот к примеру, мы начали доказательство некоторого правила, и выдали уже какой-то результат, и даже им воспользовались. Затем, обращаясь к недовычисленым данным, мы спровоцировали продолжение доказательства правила, и вдруг выясняется, что это правило не может быть доказано. Т.е. выданные на первом этапе данные не являются достоверными и ими нельзя было пользоваться.
В чисто функциональном языке такой проблемы нет, т.к. функция всегда возвращает какой-либо результат.
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
25 Jan 2012 11:52 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
Все противоречия снимаются, если логический вывод считать таким же вводом-выводом как например ввод с клавиатуры или чтение из файла - т.е. через ленивый список. Пролог ведь тоже выдав одно решение может выдать следующее, если человек нажмет ; что есть тоже самое как и ленивая выдача. Т.е. входные прологовские факты (и правила где-то сбоку) могут быть представлены как элементы ленивого списка, который по одному перебирает ленивый вычислитель, пока не найдёт первое попавшееся решение, удовлетворяющее поставленному условию - если юзер захочет следующее решение, то оно будет точно также вычислено как следующий элемент ленивого списка.
Я для начала хочу просто написать интерпретатор пролога на Hope - подобный опыт у меня есть, т.к. больше года назад для курса ИИ, который я слушал в Колумбийском Университете, я уже писал практическое задание на тему унификации и сопоставления с образцом на CommonLisp, причём в функциональном стиле.
|
25 Jan 2012 19:41 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 863
|
Об этом я тоже думал, но мне показалось, что решение, которое возвращает список из нескольких значений, и несколько решений, возвращающих данные списка поэлементно, это не одно и то же. В прологе предикат может возвращать, например, числа от 1 до n либо как несколько решений, либо как список чисел от 1 до n.
Предположим, что некий предикат имеет три подцели, каждая из которых возвращает "ленивый" список. Далее этот предикат как-то работает с этими списками, но это вовсе не означает, что он будет перебирать все тройки элементов из разных списков, как это было бы в случае, если бы подцели возвращали данные поэлементно.
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
26 Jan 2012 01:41 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
Да - при откатах придётся "перематывать" списки к началу - но это решаемо
|
26 Jan 2012 07:07 |
|
|
b2m
Devil
Joined: 26 May 2003 06:57 Posts: 863
|
А то, что успелось вывестись на консоль, тоже стирать?
_________________Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
|
26 Jan 2012 08:25 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
Ну что вывелось, то вывелось - откаты и перемотки нужны для вычисления следующего ответа
|
26 Jan 2012 17:22 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22583 Location: Silicon Valley
|
Случайно купил на амазоне дешёвую книжку про совмещение логического программирования и функционального программирования, причём в отличном состоянии:
Christian Prehofer. Solving Higher-Order Equations: From Logic to Programming. 1998
|
19 Apr 2012 14:48 |
|
|