Nice TWiki > Doc > LanguageComparisons > NiceVersusPizza > AlgebraicDatatype (r1.10) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
I think that it would be very convenient to have access to good old algebraic datatypes in Nice, perhaps modified as described in this article: (Extensible Algebraic Datatypes with Defaults)

It should be allowed to do a switch on an algebraic datatype (otherwise there is no reason to include the feature ;-).

I would say that it is easy to implement this feature - one might be able to get away with a simple translation to existing language features: just introduce a new multifunction for each switch statement. But I might be missing something....

-- TorbenHoffmann? - 08 Jul 2002

A problem with swich statements is that they are closed: if you add a new case to your datatype, you have to modify all switches operating on this datatype. It seems the paper presents well this problem, and tries to solve it with default cases (I have only skipped through the first pages so far).

I think multi-methods nicely solve this problem. Let's try to see if something could be improved. Taking their example:

package expressions;

abstract class Expression {}
class Variable extends Expression { String name; }
class Lambda extends Expression { String var; Expression body; }
class Apply extends Expression { Expression function; Expression arg; }

Expression eval(Expression);
eval(Variable v) = v;
eval(Lambda l) = l;
eval(Apply a) = apply(eval(a.body), eval(a.arg));

Expression apply(Expression, Expression);
apply(Lambda l, v) = substitute(l.body, l.var, v);
apply(e1, e2) { throw new Error("Not a function: " + e1);

package numeric;

import expressions;

class Number extends Expression { int value; }
class Opposite extends Expression {}

eval(Number n) = n;
apply(Opposite o, Number n) = new Number(value: - n.value);

package print;

import expressions;

String display(Expression);

package main;
import expressions;
import numeric;
import print;

display(Number n) = n.value.toString();
display(Opposite o) = "-";

(I choose Opposite instead of Plus for simplicity of implementation, but the idea is the same)

What do you object to this solution?

A small change could to to allow a shortcut for the definition of an abstract class and several simple subclasses:

class Expression = 
    Variable { String name; }
  | Lambda   { String var; Expression body; }
  | Apply    { Expression function; Expression arg; }

This would be equivalent to the first version, but somewhat easier to read. As for switch, I think method implementation is as elegant, and more general because of the possibility to add new cases. Objections?

-- DanielBonniot? - 10 Jul 2002

Thanks - you have enlarged my understanding of multimethods.

I can see how method implementation is more general due to the possibility of adding new cases, but I am missing one good thing about algebraic datatypes in connection with case statements: the compiler warns you if you have not covered all the types in the union. That forces you to update all over the place when you add a case to an algebraic datatype which has it merits and its demerits, admittedly.

In Nice, if you add a new case (a new subclass of the root class), the compiler will indeed warn you if this case is not covered by an existing implementation for each method. -- DanielBonniot?

As I was pondering over your answer I thought of something that might be of practical use: let the compiler generate information about how the functions handle the different sub-types of a specific super class. Eg, if you take the Person example from the tutorial you the compiler should generate the following information:

   worker -> worker
   person -> person

and if you add another person sub-class, say Manager, but do not create a display(Manger m) function the compiler should output something along the lines:

   worker -> worker
   person -> person
   manager -> person WARNING: super function used.

Then you still have the flexibility of multimethods but regain some of the extra checks that is inherent in ML-style algebraic datatypes.

Keep up the good work. -- TorbenHoffmann?

Are you suggesting to display this information systematically when an implementation from a super-class is used? This situation might be new to functional programming people, but I think it is normal and desirable often with OO languages. However there are cases where you want implementation to be done for sub-classes. It is possible using the # keyword:

String display(Person);
display(#Person p) = ...;

Then if you declare a sub-class of Person, it is not matched by the implementation #Person, so the compiler enforces that a new one be given.

-- DanielBonniot? - 28 Aug 2002

I don't think the closed nature of switch statements and algebraic data types is necessarily bad. Aren't some classes naturally closed?

Take the standard AST visitor, for example. I think you'd want the compiler to complain about all your switch statements when you add a new member to the class. If that results in too many error messages, you could add a "default" case during development to make the compiler shut up. But after you've implemented all the cases, the compiler can also warn you that the "default" case is unreachable and that you can safely remove them.

There seems to be something distinctly different about closed classes that would makes it undesirable to mimic them with regular OO classes. To me, it seems like most uses of "instanceof" (or even multi-methods) are not designed for open classes. Open classes should be dealt with using their public interface only, relying only on virtual methods for polymorphism. Using multi-methods with open classes seems like an unnecessary weakening of static type safety.

ML-style types shouldn't be adopted directly, of course. They're lacking many of the fundamental OO features that would be required for them to "fit" in an OO language. Once the features are added, I think they'll fit in quite well with the Nice language.

On advantage of introducing closed classes is that enums are now just a degenerate case of closed classes, adding uniformity to the type system.

-- KannanGoundan - 15 Oct 2004

For the AST example, if you implement it with multi-methods you also get the error messages if you add a new class without an implementation for it.

Could you give an example of why you think multi-methods lead to a weakening of static type safety? (Keep in mind that a multi-method defined in another package as a class will not have access to the private members of the class, so encapsulation is not broken).

Actually, now with enums with have a form of closed classes. I'm not sure why they are "degenerate". What difference do you make between enums and closed classes?

-- DanielBonniot - 16 Oct 2004

Degenerate Enums

From what I can tell, Nice enumerations are implemented using object instances (which is also what Java 1.5 does, I believe). If you had the following enum:

enum Color = Red | Green | Blue

It would be translated to something like:

class Color {
   private Color() {}
   public static final Red = new Color();
   public static final Blue = new Color();
   public static final Green = new Color();

That translation only works because enums are not treated like a case of general union types. If they were, I'd expect the translation to be something like:

class Color {}
  private Color() {}
  public static class Red extends Color {
     private Red() {}
     private static final INSTANCE = new Red();
     public static Red make() { return INSTANCE; }
  ... Green ...
  ... Blue ...

// Constructors are private to prohibit external code from subclassing us.
// Use the 'make()' wrapper to construct instances.

The advantage of the second translation technique is that it can also be used to encode more complex union types:

type Expr = Abst(String param, Expr e) | App(Expr e1, Expr e2) | Ident(String s) | Zero | Succ

// Compiles to:
class Expr {
   private Expr() {}
   public static class Add extends Expr {
      public final Expr e1, e2;
      private App(Expr e1, Expr e2) {
         this.e1 = e1;
         this.e2 = e2;
      public static Add make(Expr e1, Expr e2) { return new Add(e1, e2); }
   ... Sub ...
   ... Ident ...

   // These two are just like enum options
   ... Zero ...
   ... Succ ...

Enums are actually just very simple union types. They never contain any data values. All the information is in the type label (which means, for example, that you can't have two distinct Red objects).

Type safety

Even though Nice will check to make sure you have covered all the cases, this guarantee is only valid at the time of compilation. After you've compiled and deployed your function, somebody might extend the AST class and pass in an unexpected type. You can protect against this using access control tricks and wrappers around the constructor (like the enum translation) but I would prefer a declarative technique. The "closedness" of a class is an important property and seems like it should be mentioned as part of a class' public interface.

-- KannanGoundan - 17 Oct 2004

About enums, I agree that they should be extended to allow arbitrary fields. That would them make exactly like closed classes.

About type safety: there are indeed issues when you use dynamic loading, or using together code that hasn't been compiled together. But to be fair problems happen equally without multimethods. Taking your example of extending the AST class, if you needed a multi-method in a language that does not support them, you would have resorted to implementing a method with instanceof tests and casts. Now with the extension this code becomes incorrect, and it will fail at runtime. With multi-methods, you could at least properly detect this condition. Better, a clever linker could even gather the declarative information in all the extensions (the method implementations) and put them together to regenerate correct dispatch code. So multi-methods actually make possible a higher degree of type safety than mono-methods.

-- DanielBonniot - 20 Oct 2004

I agree that Java is lacking features to handle the AST Visitor. However, I think multimethods are are the less-safe solution (as opposed to union types). Nice tries to make things safer (since the compiler warns you about unhandled cases), any time OO-style dynamic dispatch crosses compilation unit boundaries, you're in trouble. This can even happen with single-dispatch:

abstract class Vehicle {}
class Car : Vehicle {}
class Boat : Vehicle {}

And in another compilation unit:

void handleVehicle(Vehicle v);
handleVehicle(Car c) { print("Car"); }
handleVehicle(Boat b) { print("Boat"); }

If you add another Vehicle type, the handleVehicle could die with a compiler-inserted runtime error. Though you could provide a default, sometimes a default doesn't make sense.

The reason I'm so stuck on union types is that they're safe. Though different-compilation-unit-dynamic-dispatch feels a little more flexible, I think union types will handle most situations just fine. Can you think of particular situations where union types aren't good enough?

-- KannanGoundan - 30 Nov 2004 生物反应器 展示架 审计 税务 不锈钢 打印机 钢结构 计算机 加盟 建筑材料 旅行社 企业管理 人力资源 网页设计 市场营销 室内设计 手机 饲料 涂料 卫星电视 物流 远程教育 展览 包装机械 包装设计 玻璃钢 瓷砖 地板 电池 电动工具 电话 电缆 电器 电线电缆 电源 雕塑 耳机 二手电脑 二手房 发电机 防盗门 纺织 机票 复印机 钢铁 工程机械 广告设计 继电器 家电 建筑设计 交换机 洁具 开关 乐器 木地板 皮革 啤酒 润滑油 摄像机 摄像头 数码摄像机 塑料机械 体育用品 网络电话 望远镜 文具 五金工具 显示器 相机 香水 蓄电池 仪表 中央空调 珠宝 平面设计 传感器 摩托车 玻璃 电机 工艺品 化工 化妆品 机械 空调 时装 食品 塑料 陶瓷 玩具 五金 印刷 轴承 钢材 汽车配件 橡胶 变压器 订房 订票 水处理 显示屏 礼品 旅游 汽车 服装 电影 数码相机 稳压器 招聘 触摸屏 机柜 酒店预定 模具 在线电影 笔记本 虚拟主机 管理咨询 域名注册 成人电影 肾病 免费电影 肿瘤 显微镜 婚介 股票 交换机 糖尿病 企业邮箱 乙肝 对讲机 化妆品 股骨头坏死 电子商务 网站推广 美女 UPS 液晶 尿毒症 条码打印机 电脑 家具 投影幕 服饰 网站空间 轮胎 网上购物 化学试剂 媒体 手套 二手笔记本 发动机 免费下载电影 水泥 塑料制品 机床 免费音乐下载 随身听 防水材料 纺织机械 耐火材料 肺结核 肺炎 风机 家居装饰 脱发 钢板 汽车美容 网络电话 监理 减速机 钢板网 钢管 网络设备 洗衣机 显卡 刀具 电视机 锅炉 二手车 滑板 眼镜 办公用品 防盗门 仪器 保温材料 继电器 变频器 办公家具 货运 高尔夫 叉车 插件 超声 泳装 箱包 小提琴 冲压 除湿机 油漆 小尾寒羊 元器件 磁性材料 刺绣 运动鞋 型材 打火机 打折机票 灯泡 电子产品 电子技术 垫仓板 吊钩 吊网 合成纤维吊装带 烘干机 胶带 结核 咖啡 空压机 冷却塔 热水器 日用品 乳品机械 石材 食品机械 收音机 手表 化工原料 多电脑切换器 茶叶 医疗设备 微型打印机 饮水机 污水处理 印刷机 冰箱 财务软件 彩钢板 音响 仓储 木制品 遥控器 摄影器材 数码产品 床上用品 面料 拉链 机箱 包装材料 涂装 水表 管理培训 门窗 破碎机 自动门 自吸泵 硬盘 绿色食品 燃气设备 容器 软管 木业 膜结构 石墨 条形码 帐篷 女装 食用菌 指纹 真空泵 喷雾干燥 喷雾干燥机 聚丙烯 聚乙烯 制药机械 汽车空调 水泵 水产 器材 汽车音响 胸罩 休闲服饰 丝网 虚拟仪器 照相机 挖掘机 袜子 白酒 半导体 单片机 钢琴 玻璃制品 装潢设计 投影机维修 混凝土 气动元件 饮料机械 聚醚 液压元件 铝合金 除尘器 珠宝首饰 焊锡 模板 消防 标准件 线切割 示波器 公司注册 防静电地板 金属 橱柜 塑料模具 树脂 雕刻 厨具 分析仪器 无线网 蝶阀 空调配件 红木 超声波清洗机 焊接设备 保护膜 电子白板 液压机械 制氧机 厨房设备 电镀 集成电路 产品设计 汽车零部件 针织 冶金 数字监控 数控机床 清洁设备 空气净化 起重机 发电机组 视频电话 视频监控 电视会议 防腐 壁球 胶粘带 售饭机 热交换器 柴油发电机组 会展 热敏电阻 电容 灯光 地毯 制冷设备 铜管 自行车 无纺布 丝绸 防雷 雕刻机 可视电话 人力资源管理 电动机 文胸 柴油机 造纸 有机玻璃 染料 连接器 空气压缩机 管件 电脑维修 电话机 摩托车配件 葡萄酒 五金机械 低压电器 包装设备 过滤器 橡塑 液压机 温湿度 管道 催化剂 电子秤 电加热器 开关柜 建材机械 保险柜 电路板 乳胶漆 工程塑料 特许经营 楼宇自控 喷码机 液位计 聚丙烯酰胺 电磁铁 超市设备 薄膜开关 指纹考勤 渔具 跑步机 防腐设备 锁具 弹簧 纸箱 煤炭 保龄球 家用电器 植绒 钻头 冲压件 建筑机械 实木地板 捏合机 整流器 酒店用品 升降台 转换器 软件下载 喷砂机 制罐 工业炉 生产线 瓷器 搅拌机 印刷机械 综合布线 避雷器 减震器 色织 燃烧器 机电设备 防雷器 地坪 纸品 冷弯型钢 木工机械 物流设备 铁塔 非开挖 热电偶 保险箱 吸塑机 喷漆 过滤材料 电刷 冷水机 采暖 机械加工 照相器材 电镀原料 毛毡 交通设施 消毒机 压滤机 刻字机 接口转换器 电视电话会议 贴纸相机 橡胶机械 喷泉设备 丝印 精细化工 塑胶玩具 五金模具 电子设备 企业形象设计 指纹识别 搬运车 牛仔布 电动车配件 会议系统 终端服务器 录音笔 球磨机 园林设计 路由器 手套箱 实验室设备 童装 手机美容 户外用品 证卡 机床附件 彩电 酒店管理 电话录音 油墨 布线 蜡烛 印刷包装 表面活性剂 节能灯 调味品 齿轮 高压泵 红外热像仪 塑料托盘 吊带 工业锅炉 反光材料 印刷设备 足球推介 热处理 压铸 商标注册 喷灌 逆变器 输送带 锻造 车库门 体育器材 太阳能热水器 绝缘材料 焊管 鼓风机 试验 插座 艺术品 矿山机械 图像监控 无缝钢管 激光切割 标签打印机 燃气表 手机配件 卫星定位 印染 玻璃机械 铝型材 注塑 液压升降机 打标机 工具柜 焚烧炉 电力设备 干燥剂 计量泵 程控交换机

wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh wire mesh

Topic AlgebraicDatatype . { Edit | Attach | Ref-By | Printable | Diffs | r1.13 | > | r1.12 | > | r1.11 | More }
Revision r1.10 - 22 Jan 2005 - 03:07 GMT - LiYan
Parents: WebHome > LanguageComparisons > NiceVersusPizza
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.