论坛首页 → 综合技术论坛 →

SQL 与函数式编程

浏览 13263 次
锁定老帖子 主题：SQL 与函数式编程
精华帖 (0) :: 良好帖 (8) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • night_stalker
  • 等级: 五星会员
  • 性别:
  • 文章: 1366
  • 积分: 780
  • 来自: 杭州
   发表时间：2009-04-19   最后修改：2009-04-20
SQL 不愧是关系代数的产物，写出来就是赤果果的函数式编程。
看这个语句： 
select * from topics where id < 12


把 topics 表看做一个 list，对应的命令式写法就像这样： 
List<Topic> searchResult = new ArrayList<Topic>();
for(Topic topic : topics){
  if(topic.id < 12){
    searchResult.add(topic);
  }
}
return searchResult;


但 select 本质上就是 filter 语句，在 Haskell 中可以写成： 
filter (\x -> (id x) < 12) topics


或者： 
[x | x <- topics, (id x) < 12]


而在 ActiveRecord 中对应查找方式是： 
Topic.find :all, :conditions => ["id < ?", 12]


比较令人不爽，写成下面这样不好多了？ 这才是 SQL DSL 嘛。 
Topic.select(:all){ :id < 12 }


设想：将 block 解析成为 s-exp，然后翻译成 SQL 字符串。（s-exp 是一个数组套数组的结构，写出来就像 Lisp 程序一样，很适合用来做代码转换或者求值）

这里提一提 ruby 中实现 s-exp 的简单原理：
在一个新对象中对 block 求值，通过此对象的 method_missing 方法产生数组： 
def method_missing meth, *args
  [meth, args]
end

实际上要复杂一些，还要反定义一些核心类的操作符等。(更全面、充分、快速的就要用到 parse tree 库了)

基本可用的一个 sxp.rb 如附件(by Robin Stocker)。尝试一下： 
irb(main):001:0> require 'sxp.rb'
=> true
irb(main):002:0> id_max = 12
=> 12
irb(main):003:0> sxp{:id < id_max}
=> [:<, :id, 12]


工作良好，也能辨认闭包变量，再写一个 s-exp 到 sql string 的翻译器就行了。 

class Symbol
  def to_sql_method
    {
      :==   => '=',
      :_and => 'AND',
      :_or  => 'OR',
      :_not => 'NOT'
    }[self] || self
  end
end

def build_sql arr
  return arr.to_s unless arr.is_a? Array
  meth = arr.shift
  meth_s = meth.to_sql_method
  params = arr.map {|e| build_sql e}
  if params.empty?
    "#{meth_s}"
  elsif SxpGenerator::BINARY_METHODS.index meth
    "(#{params[0]} #{meth_s} #{params[1]})"
  else
    "#{meth_s}(#{params.join ','})"
  end
end

def Topic.select *options, &block
  Topic.find options, :conditions => build_sql(sxp &block)
end


带 and 的使用方式： 
Topic.select(:all){ _and(:id < 12, :id > 5) }


这个实现比较 naive，不能辨认多行语句，and or 暂时只能前缀，也没有检查更多的 sql 函数……

不过我的目的只是证明这种语法在 ruby 中是可以实现的。

一般的数据库的使用方式是要通过 SQL 拼接的：
逻辑 <--> ORM 框架、DAO 等 <--> SQL字符串 <------> 解析 SQL <--> 数据库 API 调用

再进一步，对支持函数式编程的语言，为什么不直接一点，跳过生成 SQL 字符串这步呢？
估计很多数据库操作的速度都会提升，也不会出现千奇百怪的 SQL 拼接法：
逻辑 <--> 解析逻辑（语言编译器/解释器） <------>  数据库 API 调用

补充： 看了 FX 的回帖，有点明白这个字符串形式调用的好处了。
不过同一个进程/嵌入式的话，还是提供 select + 函数指针接口比较好呢。
  • sxp.zip (601 Bytes)
  • 下载次数: 25
返回顶楼
         
  • QuakeWang
  • 等级: 五钻会员
  • 性别:
  • 文章: 854
  • 积分: 2516
  • 来自: 上海
   发表时间：2009-04-19  
在ActiveRecord上有类似的adpater:
http://defunkt.github.com/ambition/adapters/activerecord.html
返回顶楼
          回帖地址
0 请登录后投票
  • night_stalker
  • 等级: 五星会员
  • 性别:
  • 文章: 1366
  • 积分: 780
  • 来自: 杭州
   发表时间：2009-04-19  
我的意思不是 OODB （和 OO 完全没联系）。

现在的数据库 API 基本都使用 SQL，不管怎么搞，最后都是发送 SQL 到 DB，
大家也习惯了 DB 后面完全是黑箱，也习惯了只用 SQL 字符串和 DB 交互。

但数据库接受到 SQL 后，还得解析这个字符串，并调用更底层的函数（可惜这些都不在数据库 api 中）。

Topic.select(:all){ :id < 12 }
和 select * from topics where id < 12
语义上是同构的，但是 Ruby 解析器和 sql 解析器之间被一堵墙隔着，
它们没法共享语法解析的结果，只能再次重复解析一遍 ……
返回顶楼
          回帖地址
0 请登录后投票
  • 花花公子
  • 等级: 四星会员
  • 性别:
  • 文章: 552
  • 积分: 418
  • 来自: 上海
   发表时间：2009-04-19  
night_stalker 写道
我的意思不是 OODB （和 OO 完全没联系）。

现在的数据库 API 基本都使用 SQL，不管怎么搞，最后都是发送 SQL 到 DB，
大家也习惯了 DB 后面完全是黑箱，也习惯了只用 SQL 字符串和 DB 交互。

但数据库接受到 SQL 后，还得解析这个字符串，并调用更底层的函数（可惜这些都不在数据库 api 中）。

Topic.select(:all){ :id < 12 }
和 select * from topics where id < 12
语义上是同构的，但是 Ruby 解析器和 sql 解析器之间被一堵墙隔着，
它们没法共享语法解析的结果，只能再次重复解析一遍 ……


sequel里面的写法是 
Topic.filter(:id < 12).all

或者 
DB=Sequel.connect(...)
DB[:topics].filter(:id < 12).all
返回顶楼
          回帖地址
0 请登录后投票
  • night_stalker
  • 等级: 五星会员
  • 性别:
  • 文章: 1366
  • 积分: 780
  • 来自: 杭州
   发表时间：2009-04-19   最后修改：2009-04-19
看了下 sequel 的源代码，就结果而言，大家都是生成 sql 字符串，完全不理会数据库这个黑箱里头是什么 ……

我希望数据库能提供类似这样的 API： 
char* select(char* from, char* scope, int (*predicate)(Record*));

（predicate是函数指针）

这样就不需要解析 s-exp，不需要拼接字符串，直接传给它一个函数即可。
数据库也不需要解析 sql，大家都舒服，效率也能提升。

而且更重要的一点：易于扩展查询条件。

折衷一点方法是传一个语法解析树... 大概像这样： 
char* select(char* from, char* scope, Node* ast_root);
返回顶楼
          回帖地址
0 请登录后投票
  • dogstar
  • 等级: 三星会员
  • 性别:
  • 文章: 376
  • 积分: 312
  • 来自: 杭州
   发表时间：2009-04-19  
sql就是在一个集合上做一些,查找,排序,筛选的操作.

fp呢,显而易见的也是在一定的集合上做操作.比如列表自省,filter,map,这些.

从这点来看,确实相似的地方.
返回顶楼
          回帖地址
0 请登录后投票
  • RednaxelaFX
  • 等级: 二钻会员
  • 性别:
  • 文章: 576
  • 积分: 1110
  • 来自: 海外
   发表时间：2009-04-19  
night_stalker 写道
看了下 sequel 的源代码，就结果而言，大家都是生成 sql 字符串，完全不理会数据库这个黑箱里头是什么 ……

我希望数据库能提供类似这样的 API： 
char* select(char* from, char* scope, int (*predicate)(Record*));

（predicate是函数指针）

这样就不需要解析 s-exp，不需要拼接字符串，直接传给它一个函数即可。
数据库也不需要解析 sql，大家都舒服，效率也能提升。

而且更重要的一点：易于扩展查询条件。

折衷一点方法是传一个语法解析树... 大概像这样： 
char* select(char* from, char* scope, Node* ast_root);

哈哈，问题就在于“代码执行的位置”。
如果你写的函数都是在同一个进程里执行的，那什么问题都没有，用函数指针传递回调函数非常直观；
如果写的函数要被另一个进程回调，那至少要涉及IPC（Inter-Process Communication），这就不是传递函数指针那么简单了。Unix系的小工具经常是用管道接起来的，而且它们经常是向管道里写文本的；
如果写的函数要被远程服务器回调，那么相关的技术就多了——RPC，RMI等一系列的东西发展了那么久，结果SOAP还是选用文本作为传递格式了（XML毕竟是文本，解析颇耗时）。选用文本也还是考虑到可互操作性；
如果写的函数根本就不是被回调，不是在自己的机器上执行，而是要在远程服务器上执行，那把函数写死在自己的代码里编译为二进制代码之后，服务器要如何运行它呢？你可以把二进制代码“序列化”，传到服务器上，但如果服务器运行的平台与自己的平台不是一样的，那在“序列化”的时候就必须考虑到服务器的平台而采取相应的交叉编译（cross-compilation）。这就不是好玩的事情了。

在数据库执行查询的使用场景，可以覆盖上述的多种情况。
可以假想有非常轻量的数据库，其完整功能是通过动态链接库接到客户进程中的。那么事情就不麻烦。
如果数据库有专属的进程在管理着，而发出查询的进程与数据库进程在同一台机器上，那么或许可以通过某种IPC来解决。
如果数据库运行在远程服务器上，那如果要做远程回调，就意味着服务器要把整个数据集传到发出查询的这边，让回调函数处理（过滤之类）；这样会占用大量带宽，显然不是好办法。所以还是让查询在服务器上进行，然后再把结果集返回过来就好。而上面提到了，编译成二进制之后再传到服务器上不是个好办法。

那么还是用.NET的LINQ为例。LINQ可以根据中间处理过程的不同，分为两种：in-memory query和remote query。其中LINQ to Object、LINQ to XML之类的都是in-memory的，而LINQ to SQL、LINQ to EF等则是remote query。
In-memory方式的LINQ中的“查询运算符”（query operator，LINQ中是这么称呼Select、Where等方法的）接受的参数是委托，也就是类型安全的函数指针。委托指向的东西可以看成是“黑乎乎的二进制代码”，便于就地执行但不便于分析。
Remote方式的LINQ的“查询运算符”接受的参数则是Expression Tree。以LINQ to SQL为例，像这样的代码（假设persons是一个用于LINQ to SQL的IQueryable）： 
from p in persons
where p.City == "Shanghai"
select p

解除语法糖之后是： 
persons.Where(p => p.City == "Shanghai").Select(p => p)

其中Where和Select里的lambda表达式都会由编译器转变为生成对应Expression Tree的代码。这些Expression Tree由LINQ to SQL的query provider分析并转变后，变为类似： 
SELECT * FROM persons WHERE city = 'Shanghai'

这样这个SQL查询就可以送到数据库所在的服务器上，在服务器上执行查询，然后服务器返回结果集到应用程序这边。使用文本传送查询表达式解除了多种耦合（硬件指令集差异、操作系统差异、数据库提供的API的差异等），代价是损失一定效率。但数据库查询本身就是重量级的I/O操作，拼装和解析文本与I/O相比只能算是零头。

Remote方式的LINQ有非常多的可能应用场景，例如说把用C#写的代码变成在客户端浏览器上运行的JavaScript。这种应用只靠函数指针是做不到的。

使用可分析的中间形式来表示代码逻辑有诸多好处，S-expr虽然在LISP就有了，但其思想在主流语言里还没得到足够充分的利用。LINQ只是这种思想的一个应用实例而已。
返回顶楼
          回帖地址
2 请登录后投票
  • RednaxelaFX
  • 等级: 二钻会员
  • 性别:
  • 文章: 576
  • 积分: 1110
  • 来自: 海外
   发表时间：2009-04-20   最后修改：2009-04-20
night_stalker 写道
补充： 看了 FX 的回帖，有点明白这个字符串形式调用的好处了。
不过同一个进程/嵌入式的话，还是提供 select + 函数指针接口比较好呢。

在内存越来越便宜、64位机器越来越普及的因素推动下，完整的in-memory DB不也在逐渐流行么。对于这种应用，你说的“提供 select + 函数指针接口”的方式就很合适。恕我还是要拿LINQ做例子，因为它用于解释这些应用场景真的非常合适。假如还是有一个persons集合，但这次是一个IEnumerable<Person>而不是IQueryable<Person>，那么前面回帖中的代码： 
from p in persons
where p.City == "Shanghai"
select p

同样还是解除语法糖变为： 
persons.Where(p => p.City == "Shanghai").Select(p => p)

这次那两个lambda表达式就分别被编译为Func<Person, bool>和Func<Person, Person>类型的两个匿名方法。
于是这个查询的执行过程简化后就像这样： 
private static IEnumerable<Person> Demo() {
    // 声明两个委托（类型安全的函数指针）
    Func<Person, bool> perdicate = p => p.City == "Shanghai";
    Func<Person, Person> selector = p => p;

    foreach (var p in persons)
        if (predicate(p))
            yield return selector(p); // 用generator来做惰性求值
}

这就跟你想要的语法和执行方式相当吻合了。而这就是LINQ to Object实现的功能。

如果什么时候.NET上有非常流行的in-memory DB出现的话，肯定会有对应的LINQ API来作为访问的接口。其它支持高阶函数的语言要支持类似的应用也不会很难。
返回顶楼
          回帖地址
0 请登录后投票
  • inshua
  • 等级: 二星会员
  • 性别:
  • 文章: 111
  • 积分: 250
   发表时间：2009-04-20  
其实 SQL 和 Prolog 更相近。一般的 fp 都有些集合功能，但集合功能不是 fp 的核心功能。
返回顶楼
          回帖地址
0 请登录后投票
  • whaosoft
  • 等级: 一星会员
  • 性别:
  • 文章: 3179
  • 积分: 100
  • 来自: 北京
   发表时间：2009-04-21  
Python 和 ruby 有什么联系吗 ?? 我只会java~
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics