神刀安全网

The Pastiche Test

May 1, 2016

I’d like to coin a term for an old but (to my knowledge) previously nameless idea.

When discussing the primitive constructs of a programming language, there is a litmus test for evaluating the quality of their design: can I implement a wrapper for the construct that looks and behaves exactly the same as the original, modulo the name? Passing this test is a good property for a language construct to have; it means the programmer has the power to substitute the construct with their own equally powerful ones.

Examples

Conditionals are a good motivating example. In Common Lisp, if is a special form that does what you expect:

> (if t (print "hello") (print "world")) hello  > (if nil (print "hello") (print "world")) world

You can define a macro that works the same way:

> (defmacro test (condition then &rest else)     `(if ,condition ,then (progn ,@else)))  > (test t (print "hello") (print "world")) hello  > (test nil (print "hello") (print "world")) world

Ruby also has if :

> if true then puts 'hello' else puts 'world' end hello  > if false then puts 'hello' else puts 'world' end world

As far as I know, there is no way to implement if yourself in Ruby. Of course, you can implement a similar construct using procs:

> def test(condition, a, b=Proc.new {})     if condition then a.() else b.() end   end  > test(true, -> { puts 'hello' }, -> { puts 'world' }) hello  > test(false, -> { puts 'hello' }, -> { puts 'world' }) world

But that doesn’t pass the test, because the usage is different from if ; you have to wrap the branches in Proc s. So if passes the pastiche test in Common Lisp, but not in Ruby. Looping constructs can be classified in the same way—can you mimic a for loop in your language?

Here’s another example. In Haskell, I can define a custom binary operator with the same “fixity” (precedence and associativity) as + :

original = putStrLn $ show $ 3 + 4 -- prints 7  infixl 6 @@ (@@) = (+) pastiche = putStrLn $ show $ 3 @@ 4 -- also prints 7

But there is no way to do this in C. So Haskell’s + passes the pastiche test, but C’s + does not.

In statically typed languages, types are a common source of pastiche failures. For example, Go’s map is an associative array type that is parametric in its key and value types:

var m map[string]int = make(map[string]int) m["answer"] = 42 var answer int = m["answer"]

But there is no way to implement map yourself in a type-safe way, because Go doesn’t have generics. In contrast, C++ has unordered_map , which is typically implemented in C++ itself. So Go’s map fails the pastiche test, but C++’s unordered_map passes.

Definition

Here is my attempt at a good definition for the term:

In a given language, a construct passes the pastiche test iff it is possible to define an extensionally identical construct in the language under a different name, optionally using the original construct in the implementation.

In this definition, “language” does not necessarily mean “programming language”—it could mean “domain-specific language”, “natural language”, or any kind of language in which it is possible to define abstractions.

“Extensionally identical” means the imitation construct is observably indistinguishable from the original in syntax, usage, behavior, asymptotic complexity, etc. To the user, only the name is different.

The “optionally using the original construct in the implementation” part means that a simple wrapper suffices. It is not necessary to implement the construct from scratch.

Related concepts

Here are some related ideas which already have names:

First-class citizen : This refers to the ability for an entity to be stored in variables, passed as an argument to functions, etc. For example, functions are first-class citizens in most modern programming languages. In some programming languages , types are also first-class citizens.

Reification : The act of exposing an abstract aspect of a system as a first-class citizen. For example, in homoiconic languages, the structure of a program is reified as an abstract syntax tree which can be manipulated by the program itself. In languages with eval , the interpreter or compiler itself is reified.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » The Pastiche Test

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址