Hopelog - гибрид Hope и Prolog

Использование и разработка софта (преимущественно на ПЦ)

Moderator: Shaos

User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

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, число, массив, объект
}
Я тут за главного - если что шлите мыло на me собака shaos точка net
7400
Maniac
Posts: 254
Joined: 14 Jul 2011 02:18
Location: Гомель

Post by 7400 »

а можно увидеть листинг средненькой программы? :)
хорошоб добавить новых типов например сверхдлинный тип интеджер аля 512 байт
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Post by b2m »

Shaos объединил эти два сообщения в одно и оставил тут, т.к. они достаточно правильно отражают мотивацию :)

У Hope и Prolog есть одна общая черта: вычисления производятся путём сопоставления с образцом и выполнения соответствующих этому сопоставлению действий. Однако, многие (может даже и все) реализации Prolog-а не используют lazy (отложенных) вычислений, которые есть в Hope, а в Hope нет возможности выполнять унификацию переменных при сопоставлении и выдачи нескольких результатов при успешном сопоставлении с одним образцом.

Да, забыл ещё сказать: в Prolog-е нельзя описывать функции. Там все арифметические вычисления производятся встроенным предикатом "is", и изменить его, с целью добавления подобной функциональности, никак нельзя.
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

7400 wrote:а можно увидеть листинг средненькой программы? :)
хорошоб добавить новых типов например сверхдлинный тип интеджер аля 512 байт
Листинг увидеть пока не получится, т.к. я ещё не определился с тем, как это всё должно сосуществовать вместе. По поводу интов неограниченной длины - да, можно сделать (как в CommonLisp) - но позже.

Ещё из идей - возможность хранения набора прологовских фактов в реляционной базе данных - например SQLite. Но это сильно потом - т.к. оно будет только на сервере (не в джаваскриптовом клиенте).
Я тут за главного - если что шлите мыло на me собака shaos точка net
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Post by b2m »

Shaos wrote:Ещё из идей - возможность хранения набора прологовских фактов в реляционной базе данных - например SQLite.
Я бы ещё промежуточные результаты вычислений в базу засунул. Если мы не хотим вычислять два раза результат функции с определёнными аргументами, то это соответстивие "аргументы->результат" надо где-то хранить. Ладно, если их не больше сотни (тогда можно и в памяти некий кэш иметь), но когда некая рекурсивная функция вызывает себя мульён раз...

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

А если мы сможем хранить в базе выражения, то можно и факты, и правила, и функции - всё хранить в базе, а интерпретатор писать на SQL :)
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

про хеши я уже размышлял в одном из функциональных топиков - тут есть свои плюсы и минусы - скорее всего нужны будут некие эвристики на тему что можно хранить, а что нет - иногда будет быстрее вычислить результат, чем ворочать ленивое выражение в памяти или базе данных
Я тут за главного - если что шлите мыло на me собака shaos точка net
7400
Maniac
Posts: 254
Joined: 14 Jul 2011 02:18
Location: Гомель

Post by 7400 »

по моему не стоит хранить результаты в базе данных
т.к. веник довольно медленный и допустим для вычисления факториала большого числа нам придется по мульену раз считывать с веника числа да причем они в базе искаться будут в этоге все это время в озу лучше все пихайте благо меньше 2 гигов этого чуда уже редко где встретиш
(если в мобилки по гигу пихают)
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

7400 wrote:по моему не стоит хранить результаты в базе данных
т.к. веник довольно медленный и допустим для вычисления факториала большого числа нам придется по мульену раз считывать с веника числа да причем они в базе искаться будут в этоге все это время в озу лучше все пихайте благо меньше 2 гигов этого чуда уже редко где встретиш
(если в мобилки по гигу пихают)
ну во-первых, во всех современных операционных системах есть такая штука как кеш - прямого побайтового доступа к файлам уже давно нет - всё кешируется и буферизируется, а во-вторых, тот же SQLite умеет работать с базами данных, хранимыми в оперативной памяти
Я тут за главного - если что шлите мыло на me собака shaos точка net
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Post by b2m »

Shaos, тебе не кажется, что ленивые вычисления, которые очень помогли бы при организации ввода-вывода, не вписываются в концепцию логического языка?

Вот к примеру, мы начали доказательство некоторого правила, и выдали уже какой-то результат, и даже им воспользовались. Затем, обращаясь к недовычисленым данным, мы спровоцировали продолжение доказательства правила, и вдруг выясняется, что это правило не может быть доказано. Т.е. выданные на первом этапе данные не являются достоверными и ими нельзя было пользоваться.

В чисто функциональном языке такой проблемы нет, т.к. функция всегда возвращает какой-либо результат.
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

Все противоречия снимаются, если логический вывод считать таким же вводом-выводом как например ввод с клавиатуры или чтение из файла - т.е. через ленивый список. Пролог ведь тоже выдав одно решение может выдать следующее, если человек нажмет ; что есть тоже самое как и ленивая выдача. Т.е. входные прологовские факты (и правила где-то сбоку) могут быть представлены как элементы ленивого списка, который по одному перебирает ленивый вычислитель, пока не найдёт первое попавшееся решение, удовлетворяющее поставленному условию - если юзер захочет следующее решение, то оно будет точно также вычислено как следующий элемент ленивого списка.

Я для начала хочу просто написать интерпретатор пролога на Hope - подобный опыт у меня есть, т.к. больше года назад для курса ИИ, который я слушал в Колумбийском Университете, я уже писал практическое задание на тему унификации и сопоставления с образцом на CommonLisp, причём в функциональном стиле.
Я тут за главного - если что шлите мыло на me собака shaos точка net
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Post by b2m »

Shaos wrote:Пролог ведь тоже выдав одно решение может выдать следующее, если человек нажмет ; что есть тоже самое как и ленивая выдача.
Об этом я тоже думал, но мне показалось, что решение, которое возвращает список из нескольких значений, и несколько решений, возвращающих данные списка поэлементно, это не одно и то же. В прологе предикат может возвращать, например, числа от 1 до n либо как несколько решений, либо как список чисел от 1 до n.

Предположим, что некий предикат имеет три подцели, каждая из которых возвращает "ленивый" список. Далее этот предикат как-то работает с этими списками, но это вовсе не означает, что он будет перебирать все тройки элементов из разных списков, как это было бы в случае, если бы подцели возвращали данные поэлементно.
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

Да - при откатах придётся "перематывать" списки к началу - но это решаемо
Я тут за главного - если что шлите мыло на me собака shaos точка net
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Post by b2m »

А то, что успелось вывестись на консоль, тоже стирать? :)
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

b2m wrote:А то, что успелось вывестись на консоль, тоже стирать? :)
Ну что вывелось, то вывелось - откаты и перемотки нужны для вычисления следующего ответа
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
Shaos
Admin
Posts: 24083
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

Случайно купил на амазоне дешёвую книжку про совмещение логического программирования и функционального программирования, причём в отличном состоянии:

Christian Prehofer. Solving Higher-Order Equations: From Logic to Programming. 1998
Я тут за главного - если что шлите мыло на me собака shaos точка net