Форум 'Декларативное программирование' на RSDN.RU

Fun with Lisp: Programming the NES

Sat, 11 Feb 2012 07:12:12 GMT

Здравствуйте.

Интересный пример метапрограммирования. Особенно для любителей низкоуровневых вещей. Давно такой искал.

[Haskell] Вышел пьяный компилятор Хаскеля 7.4.1

Tue, 07 Feb 2012 14:52:52 GMT

Информация где обычно.

Clojure + Android

Sat, 04 Feb 2012 14:47:50 GMT

Здравствуйте.

Есть ли тут андроидописатели? Насколько реально на практике использовать Clojure или ClojureScript на Android?

[Haskell] рекуррентная последовательность в списке

Sat, 04 Feb 2012 09:56:47 GMT

Есть список, в котором находится рекуррентная последовательность.
Требуется получить 1 элемент последовательности с большим номером.

Пытаюсь сделать так:

func = lst !! 1000000 -- any big number
    where
        lst = iterate (+1) 0 -- sample of sequence

main = putStrLn $ show func

При попытке выполнить падает из-за нехватки стека. Как изменить код, чтобы не падал?
(Увеличить размер стека не предлагать)

Есть вариант использовать ф-ю

strictGet cnt lst@(val:tl) = if cnt > 0 then val `seq` strictGet (cnt-1) tl else val

Но такое решение не нравится. Как можно по другому?

[ANN][F#] WebSharper стал Open-Source

Fri, 03 Feb 2012 08:23:01 GMT

Новость трехнедельной давности, но как-то здесь прошла незамеченной.

Последняя версия бибилиотеки WebSharper 2.4 основанной на компиляции F#-to-JavaScript стала Open-Source.
Модель лицензирования двойная: или AGPL со всеми вытекающими ограничениями или коммерческая лицензия.
Исходники здесь.

... << RSDN@Home 1.2.0 alpha 5 rev. 1536>>

Игрушечный SQL-образный DSL

Wed, 01 Feb 2012 15:53:29 GMT

Разбираюсь с макросистемой racket'a. Пишу SQL-образный DSL
Хочу проверять поля в where-clause на наличие у сущности, для которой делается запрос. И делать это на этапе компиляции.
Сейчас сущность объявляется как

(define-entity user 
  user_table (id name))

Что разворачивается в

(define entity 
  (hash 'table 'user_table
        'fields '(id name)))

И проверка работает только в runtime.
Т.е. при попытке обратится из syntax-case приводит к
reference to an identifier before its definition: user phase: 1 (which cannot access the run-time definition)
Как бы выйти из этой ситуации?
Использовать для определения сущности define-for-syntax?

скриптование на lisp

Mon, 30 Jan 2012 04:13:27 GMT

Для программы понадобилась система скриптования. Хочу попробовать для этого использовать lisp. Подскажите, что для этого нужно использовать.

Visual basic наследник ML?

Thu, 26 Jan 2012 07:33:08 GMT

Не раз видел упоминания об этом факте, в частности здесь http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html

1973 — Robin Milner creates ML, a language based on the M&M type theory. ML begets SML which has a formally specified semantics. When asked for a formal semantics of the formal semantics Milner's head explodes. Other well known languages in the ML family include OCaml, F#, and Visual Basic.

В упор не вижу, чего там взято из ML

[Scala] Почему не компилируется

Sat, 14 Jan 2012 16:41:16 GMT

Привет!

Читаю главу 35 Programming in Scala, 2e. Там есть такой пример:

import scala.util.parsing.combinator._

object FormulaParser extends RegexParsers {
  def number : Parser[Number] = decimal ^^ ( d => Number(d.toDouble) ) // так компилируется


/* а вот так - нет, ошибка
   error: missing parameter type for expanded function ((x$1) => x$1.toDouble)
   def number : Parser[Number] = decimal ^^ ( Number(_.toDouble) )
*/  
  def number : Parser[Number] = decimal ^^ ( Number(_.toDouble) )
}

Не понимаю, почему.

^^ определен в библиотеке как
def ^^ [U](f: T => U): Parser[U]

Пробовал на простом примере со своим классом, определяющим ^^, там прокатывают оба варианта

Монады и Uniqueness_type или Haskell, Clean и C#

Sat, 14 Jan 2012 05:24:36 GMT

Монады часто объясняют как абстрактную математическую штуку, и редко рассказывают, а что же это такое с точки зрения программиста, а так же с точки зрения реализации.

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

в первом приближении, вид функций _getline и _putline можно записать как:
(stream, line) _getline(stream),
stream _putline(stream, line).
При такой записи уже нет проблем с переходами что-то в ничего, и ничего во что-то, но из-за того, что компилятор имеет право переставлять местами вызовы возникает неопределенность в следующем коде: оба варианта вывода ab и ba получаются равнозначны.

stream F(stream)
{
  return L(_putline(stream, "a"), _putline(stream, "b")); //L - это произвольная функция вида (stream, stream) -> stream
}

руками ловить такие неопределенности неспортивно, и предлагается два способа решения этой проблемы:
1. Uniqueness type
в данном случае утверждается, что тип stream (или аналог) должен быть особым видом типов, для которых компилятор обязан проверять, что одно и тоже значение не используется два раза. и так сделано в Clean и Mercury.
и тогда на предыдущий код компилятор наругается, что переменная stream используется два раза, и заставит переписать его во что-нибудь типа:

stream F(stream) {return _putline(_putline(stream, "a"), "b");}

2. Monad
во втором случае умные люди заметили, что если разрешить комбинировать только "названия" функций, а не сами вызовы, то ситуацию с неопределенностью вообще построить нельзя.
в этом случае, в языке разрешается вызывать вспомогательные функции getline и putline вместо исходных _getline и _putline:

Func<stream, (stream, string)> getline = _getline; 
Func<stream, stream> putline(string line) {return stream => _putline(stream, line);}

тип функции getline "Func<stream, (stream, string)>" обозначают как IO string
тип функции putline "Func<string, Func<stream, stream>>" обозначают как string -> IO()
для комбинирования таких сложных типов добавляют две функции bind и return, а вызов типа "Func<stream, (stream, string)>" (и аналогичных) делается закрытым.

при этом функции getline и putline могут быть описаны с помощью Uniqueness type

Clean (или Mercury) мне лень ставить, поэтому приведу реализацию монады IO на C# (на Clean/Mercury код будет такой же с точностью до синтаксиса):

  class IO_Monad
  {

    //внутренние реализации функций _getline, _putline, Main

    private static Tuple<IBaseIO, string> _getline(IBaseIO io)
    {
      var line = io.ReadLine();
      return new Tuple<IBaseIO, string>(io, line);
    }
    private static IBaseIO _putline(IBaseIO io, string line)
    {
      io.WriteLine(line);
      return io;
    }

    private static void Main()
    {
      main()(new ReaderWriterIO(Console.In, Console.Out));
    }

    //доступные для использования объявления getline, putline, bind, return

    public static Func<IBaseIO, Tuple<IBaseIO, string>> getline = _getline;

    public static Func<IBaseIO, IBaseIO> putline(string line)
    {
      return io => _putline(io, line);
    }

    public static Func<IBaseIO, Tuple<IBaseIO, T>> Return<T>(T a)
    {
      return IBaseIO => Tuple.Create(IBaseIO, a);
    }
    public static Func<IBaseIO, Tuple<IBaseIO, Tb>> Bind<Ta, Tb>(Func<IBaseIO, Tuple<IBaseIO, Ta>> ma, Func<Ta, Func<IBaseIO, Tuple<IBaseIO, Tb>>> a_mb)
    {
      return io =>
        {
          var res = ma(io);
          return a_mb(res.Item2)(res.Item1);
        };
    }
    public static Func<IBaseIO, IBaseIO> Bind<Ta>(Func<IBaseIO, Tuple<IBaseIO, Ta>> ma, Func<Ta, Func<IBaseIO, IBaseIO>> a_mb)
    {
      return io =>
      {
        var res = ma(io);
        return a_mb(res.Item2)(res.Item1);
      };
    }

    //программа

    static Func<IBaseIO, IBaseIO> main()
    {
      return Bind(getline, putline);
    }

    //вспомогательные объявления для реализации функций _getline и _putline

    public interface IBaseIO
    {
      string ReadLine();
      void WriteLine(string line);
    }
    public class ReaderWriterIO:IBaseIO
    {
      public ReaderWriterIO(TextReader reader, TextWriter writer)
      {
        this.Reader = reader;
        this.Writer = writer;
      }
      public readonly TextReader Reader;
      public readonly TextWriter Writer;
    
      public string  ReadLine()
      {
           return Reader.ReadLine();
      }

      public void  WriteLine(string line)
      {
           Writer.WriteLine(line);
      }

    }
  }

[Scala] Как заставить map возвращать правильный тип

Mon, 09 Jan 2012 12:49:16 GMT

Привет

Изучаю Programming in scala 2e, главу про создание собственных коллекций. Там есть такой пример:

import collection.{IndexedSeqLike, IndexedSeqOptimized}
import collection.mutable.{ArrayBuffer, Builder}
import collection.generic.CanBuildFrom

sealed abstract class Base
case object A extends Base
case object T extends Base
case object G extends Base
case object U extends Base
object Base {
  private val arr = Array(A, T, G, U)
  private val map: Map[Base, Int] = Map(A -> 0, T -> 1, G -> 2, U -> 3)
  def fromInt(i : Int) : Base = arr(i)
  def toInt(b : Base) : Int = map(b)
}

final class RNA1 private(groups : Array[Long], val length : Int)
  extends IndexedSeq[Base]
  with IndexedSeqOptimized[Base, RNA1]
  with IndexedSeqLike[Base, RNA1]
  {
  
  import RNA1._

  override protected[this] def newBuilder = RNA1.newBuilder
  
  def apply(idx: Int) : Base = {
    if (idx < 0 || idx >= length)
      throw new IndexOutOfBoundsException
    val grp = groups(idx / PerElem)
    val grpNo = idx % PerElem
    val no = (grp >> (grpNo * Grp)) & Mask    
    Base.fromInt( no.toInt )    
  }
}

object RNA1 {
  private val Grp = 2
  private val Mask = 3
  private val PerElem = 64 / Grp
  
  def fromSeq(seq : Seq[Base]) : RNA1 = {
    val len = seq.length
    val groups = new Array[Long]( (len + PerElem - 1) / PerElem)
    var n = 0
    for (b <- seq) {
      groups(n / PerElem) += Base.toInt(b) << ((n % PerElem) * Grp)
      n += 1
    }

    new RNA1(groups, len)
  }
  
  def apply(elems : Base*) : RNA1 = fromSeq(elems)

  private def newBuilder: Builder[Base, RNA1] = new ArrayBuffer[Base] mapResult fromSeq

  implicit def canBuildFrom: CanBuildFrom[RNA1, Base, RNA1] =
    new CanBuildFrom[RNA1, Base, RNA1] {
      def apply(from: RNA1) = newBuilder
      def apply() = newBuilder
    }
}

Теперь если сделать так

val rna1 = RNA1(A, A, T, G, U)
println(rna1 map  {case A => G case b => b  })

то мы получим RNA1(G, G, T, G, U)
т.е. map вернет правильный тип (так как будет использован canBuildFrom из компаньона).

А вот если сделать так:

val rna1 : Seq[Base] = RNA1(A, A, T, G, U)
println(rna1 map  {case A => G case b => b  })

то мы получим Vector(G, G, T, G, U), т.е. map, вызванный для Seq[Base], вернет дефолтный динамический тип для IndexedSeq — Vector.

А как добиться того, чтобы и в этом случае вернулся правильный тип — RNA1?

10.01.12 11:13: Перенесено из 'Java'

10.01.12 23:48: Перенесено модератором из 'Java' — по просьбе автора — Blazkowicz

overloading и система модулей

Thu, 05 Jan 2012 14:26:01 GMT

В haskell есть классы типов, которые предоставляют обобщенный механизм перегрузки функций/операторов:

class Eq a where
    (==) :: a -> a -> Bool

-- теперь можно объявить оператор '==' для любого типа
instance Eq Integer where 
    x == y = integerEq x y

instance Eq foo where 
    x == y = fooEq x y

Подумалось — а что если обобщить этот механизм еще больше, вынести на уровень модулей и представить в виде семантики конструкции open (далее псевдокод):

module Foo where
    (==) :: foo -> foo -> bool
    (==) = <реализация '==' для типа 'foo'>

module Bar where
    (==) :: bar -> bar -> bool
    (==) = <реализация '==' для типа 'bar'>

open Foo
open Bar

-- теперь в области видимости у нас есть две реализации функции, и компилятор выбирает подходящую в зависимости от контекста

cmpThree :: a -> a -> a -> bool
cmpThree a b c = (a == b) && (b == c)

Преимущество — можно иметь несколько реализаций перегружаемых функций для одного типа, и легко переключаться между ними с помощью конструкции open. Если в языке есть некая система эффектов, выраженных в типах, то можно выбирать варианты функций в зависимости от эффекта аргумента — скажем, можно иметь 2 реализации map для списков — обычный и паралелльный (только для pure функций).
Непонятно, как быть при конфликте имен в случае совпадающих типов — можно, например, объявить некую функцию "функцией по умолчанию", что будет полезным например для того же параллельного map.
Непонятно, какие ограничения должны быть для перегружаемых функций, например, должны ли они иметь одинаковый principal type, арность и т.п.
Так же очевидно, что не всегда компилятор сможет эффективно выводить типы (в зависимости от ограничений на перегрузку).

Был бы очень благодарен, если кто-то укажет на существующие работы в области перегрузки функций, т.к. складывается впечатления, что кроме type classes и их расширений, никаких работ в данном направлении не было.

Неизменность объектов не напригает ли на практике ?

Wed, 04 Jan 2012 12:14:48 GMT

Сорри, но у меня ламмерский вопрос. Я сейчас пытаюсь разобраться с функциональщиной. С идеологическим выигрышем от неизменности объектов вроде всё понятно, но есть подозрения, что это явление может несколько нагибать при банальном кодировании, особенно на Эрганге. Например, отсутствие глобальных переменных или механизма замыканий на переменные выше по блоку кода заставляет проталкивать одни и те же параметры по функциям. Во-вторых, напр., требование только одиночного присваивания (или связывания со значением) подталкивает к коду вида:

...
State1 = some_func1(val1),
State2 = some_func2(val2, State1),
State3 = some_func3(val3, State2),
...

т.е., плодятся переменные для одних и тех же нужд. Хотя здесь есть защита от случайной порчи переменной, но, всё-таки, это некие проблемы при рефакторинге. В немерле, скале и им подобным есть полный арсенал императивщины, кложура тоже имеет некие глобальные объявления и контролируемую возможность правки "по месту". В хаскеле, имхо, эти проблемы менее выражены, он заставляет писать код "менее императивно", чем эрганг, т.е. дробить алгоритмы на составляющие функции, но для этого есть "let" и "where" объявления, чего нет в эрланге. Вроде бы, есть попытки упростить жизнь через монады (напр., монады состояний) и есть некий велосипед do-нотаций и для эрганга, но для неподготовленного это далеко не упрощение.

В общем, нагибает ли кодирование в таком стиле, или это всё надуманно по неопытности ?

Conduits

Fri, 30 Dec 2011 16:47:58 GMT

Iteratee уродские абсолютно (все, без исключения)
Поэтому когда я в следующий раз доберусь до компьютера, буду изучать http://hackage.haskell.org/package/conduit-0.0.0.1
Надеюсь они мне понравятся больше, чем существующие Iteratee, иначе наверное свои придётся писать.

Барби-программист

Mon, 26 Dec 2011 18:13:31 GMT

http://www.my-barbie.ru/c/3/p/8/ (третий абзац)

Вопрос про Applicative

Mon, 26 Dec 2011 13:35:38 GMT

Вопрос наверно дурацкий, но сам чего-то не осиливаю.
Если есть такой код:

 import Control.Applicative
 import Data.Monoid
 
 newtype Constant a b = Constant { getConstant :: a }
                            deriving Show

 instance Functor (Constant a) where
    fmap f (Constant x) = Constant x

 instance (Monoid a) => Applicative (Constant a) where
    pure _ = Constant mempty
    Constant x <*> Constant y = Constant (x `mappend` y)

То как это вообще может работать?
*Main> Constant (Sum 1) <*> Constant (Sum 2)
Constant {getConstant = Sum {getSum = 3}}
*Main> :t Constant (Sum 1)
Constant (Sum 1) :: Num a => Constant (Sum a) b

Ведь (<*>) :: f (a -> b) -> f a -> f b, то есть <*> требует на вход функцию в контексте, а здесь он получает совсем не функцию.

И как пользоваться pure? Пытаюсь так:

*Main> pure (Sum 1) <*> Constant (Sum 2)

<interactive>:1:7:
Couldn't match expected type `a0 -> b0' with actual type `Sum a1'
In the return type of a call of `Sum'
In the first argument of `pure', namely `(Sum 1)'
In the first argument of `(<*>)', namely `pure (Sum 1)'

Работает почему-то только так:
*Main> pure (\_->Sum 1) <*> Constant (Sum 2)
Constant {getConstant = Sum {getSum = 2}}

Почему на Haskell получается так медленно?

Wed, 21 Dec 2011 19:04:34 GMT

Доброе время суток!

Написали мы программу, которая находит первые N простых чисел и вычисляет их сумму. Написали на C и на Haskell. Алгоритм тупой, но суть в том, что он одинаковый. В результате, программа на C выполняет задачу за 4 с, а на Haskell -- за 54 c. Из опций стоит только -O2.

Почему же такая разница? Привожу исходники:

int isPrime( int num ) {
        int count = 0;
        int i = 1;
        for( ; i <= num ; ++i ) {
                if( num % i == 0 ) ++count;
        }
        return 2 == count;
}

#define COUNT 5000

#include <stdio.h>

int main( void ) {
        int count = 0;
        int num = 1;
        int sum = 0;
        for( ; count < COUNT ; ++num ) {
                if( isPrime( num ) ) {
                        sum += num;
                        ++count;
                }
        }
        printf( "%d\n" , sum );
        return 0;
}

divisors num = filter (\i -> (mod num i) == 0 ) [1..num]

isPrime num = length (divisors num) == 2

firstPrimes count = take count (filter isPrime [1..])

count = 5000

main = print $ sum $ firstPrimes count

Впрочем, видно, что вариант на Haskell весь из себя ленивый и использует списки. Я пробовал расставлять строгость (сначала обдуманно, потом где попало) -- не помогло. Затем я подглядел вариант с параметром-аккумулятором и получился вот такой (страшный) код:

incDiv num i acc | mod num i == 0 = 1+acc
                 | otherwise      = acc

divisors num i acc | i <= num  = divisors num (i+1) (incDiv num i acc)
                   | otherwise = acc

isPrime' num = divisors num 1 0 == 2

primesSum count num acc | count > 0 = if isPrime' num
                                      then primesSum (count-1) (num+1) (num+acc)
                                      else primesSum count (num+1) acc
                        | otherwise  = acc

count = 5000

main = print (primesSum count 1 0)

Однако я получил всё те же 54 с. Подскажите, пожалуйста, что я делаю не так, и возможно ли вообще в данном случае приблизить время исполнения к сишному варианту (хотя бы в два раза медленнее, но не в 13).

--
Спасибо за внимание!

yacc: правило по умолчанию

Fri, 16 Dec 2011 08:06:11 GMT

Вопрос по составлению yacc-граматики:

У меня есть лексемы слов WORD и знаков препинания: DOT COMMA etc.

Я составил правило, чтобы находить простые предложения:

sentence_begin: WORD

sentence_middle: sentence_begin
sentence_middle WHITESPACE WORD
sentence_middle COMMA WHITESPACE WORD

sentence: sentence_middle DOT

Какое правило нужно добавить, чтобы в него попадали все варианты, которые не удовлетворяют данному правилу (fail_sentence)?

Yesod Haskell web framework

Thu, 15 Dec 2011 08:13:23 GMT

Yesod is a Haskell web framework for productive development of type-safe, RESTful, high performance web applications

здесь

Кто-нибудь использовал/игрался?

Of course type-safety provides big productivity boosts by guaranteeing against typos or using wrong type in a function. But Yesod cranks this up a notch to guarantee common web application errors won't occur.

no XSS attacks — user submissions are automatically sanitized
no SQL injection — sql queryies are automatically escaped
database queries are always valid — querying is done in Haskell and uses your schema
valid template variables with proper template insertion- variable are known at compile time and treated differently according to their type
type-safe urls — say goodbye to broken links

здесь

Побаловался я тут пару вечеров с yesod/haskell.
Вчера попробовал обновить через cabal (cabal install yesod). Выдало кучу ошибок с зависимостями.
ghc-pkg check выдает теперь yesod пакеты.

Как мне сделать, чтобы опять стало все хорошо (чтобы поменьше работы было) ?
Как мне делать, чтобы в будущем таких ошибок не повторялось?

структурная рекурсия на вьюхе (view) на натуральный ряд

Wed, 14 Dec 2011 11:00:52 GMT

вот определение на псевдохаскеле:

fi(1) = 1
fi( x*prime^n ) = fi(x) * prime^(n-1) * (prime-1)

здесь ^ это оператор возведения в степень, fi это Функция_Эйлера

как его максимально красиво написать на настоящем хаскеле (красиво -- значит сохранив паттерн-матчинг)?

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