Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

McCarthy's Ambiguous Operator (2005)

randomhacks.net

Post reply on HN
Print view View original

31–40 of 43 posts

Re: McCarthy's Ambiguous Operator (2005)

#31

Post by hopler »

theoh wrote: post #17
millstone wrote: post #9

Earlier quoted context omitted.

This analogy misses something fundamental. See how the assignments to x and y are of very different character than the predicate? Notice the return path (`else []`). `amb` doesn't need this. `amb` merges the assignments and predicate - this is important because you may not know your argument count statically, i.e. if your arguments are a list. But beyond that, `amb` may backtrack an arbitrarily deep call stack, so th…

Hmmm, I think there is some subtlety here in terms of the way an empty list is used in Haskell. This paper by Wadler from the 80s (predating monads) discusses the functional lore of the combinator approach to parsing, and it significantly leverages the properties of [] to represent failure. It's a "semipredicate" type of situation, where the return value is either a list or failure; conveniently, the empty list isn't…

It's an arbitrary choice in the Prelude, yes. If you don't like it you can definitely your own Cons type (or wrap a list in a new type) and define any monad instance (semantics) you choose.

Re: McCarthy's Ambiguous Operator (2005)

#32

Post by hopler »

billsix wrote: post #28
tempodox wrote: post #22

I envy the languages with continuations. That makes the implementation of backtracking so much easier.

Continuations also allowed me to implement python’s yield/send in 16 lines of Scheme code :-) http://billsix.github.io/bug.html#_make_generator

You can also implement scheme's call/cc with python's yield/send, right?

Re: McCarthy's Ambiguous Operator (2005)

#33

Post by theoh »

hopler wrote: post #31
theoh wrote: post #17

Earlier quoted context omitted.

Hmmm, I think there is some subtlety here in terms of the way an empty list is used in Haskell. This paper by Wadler from the 80s (predating monads) discusses the functional lore of the combinator approach to parsing, and it significantly leverages the properties of [] to represent failure. It's a "semipredicate" type of situation, where the return value is either a list or failure; conveniently, the empty list isn't…

It's an arbitrary choice in the Prelude, yes. If you don't like it you can definitely your own Cons type (or wrap a list in a new type) and define any monad instance (semantics) you choose.

Cons/lists don't have to be involved at all: a Set type could be made to work for many applications.

I've observed several smart people struggling at the outset with the connection between recursively defined lists and nondeterminism in Haskell. It's not uncommon for people to assume that there is some essential connection between the two, because that's what "list monad" seems to suggest. In fact any collection type would do.

Re: McCarthy's Ambiguous Operator (2005)

#34

Post by gjm11 »

hopler wrote: post #32
billsix wrote: post #28

Earlier quoted context omitted.

Continuations also allowed me to implement python’s yield/send in 16 lines of Scheme code :-) http://billsix.github.io/bug.html#_make_generator

You can also implement scheme's call/cc with python's yield/send, right?

Not in full generality. (Well, obviously you can write a whole Scheme interpreter in Python! But you can't write something that does in Python just what call/cc does in Scheme.)

Suppose you do the following:

(define a-continuation (call-with-current-continuation (lambda (c) c)))

The value of a-continuation at this point is a continuation object that, when called with argument x, sets a-continuation to x and returns to toplevel.

So if you now do, say,

(define (showfibs a b) (print a) (if (> a 1000) (a-continuation a) 1) (showfibs b (+ a b)))

and

(showfibs 0 1)

then you'll get 011235813213455891442333776109871597 as output, the new value of a-continuation will be 1597, and you'll be back at your top-level REPL prompt.

I don't think anything you can do with Python generators has such a pervasive ability to mess with control flow.

Re: McCarthy's Ambiguous Operator (2005)

#36

Post by dragontamer »

User23 wrote: post #7
phoe-krk wrote: post #5

This actually sounds very Prologesque. "Here, have some inputs. From those, find me the ones that satisfy this goal."

AMB is a very handy primitive to implement prolog.

Hmmm... AMB probably is sufficient for a toy version of Prolog.

I feel like anyone actually implementing prolog will need to fully understand horn logic. AMB is a useful operator when the specifics of the backtracking search can be abstracted away.

But an "actual" prolog implementation needs to have a well-defined depth-first search over the horn-logic clauses. There are a lot of optimizations to make horn-logic solvers way faster.

Re: McCarthy's Ambiguous Operator (2005)

#37

Post by Dylan16807 »

hopler wrote: post #30
Dylan16807 wrote: post #16

Earlier quoted context omitted.

That's not an amb function. That's a builtin type that's inherently amb-y. You still get credit for solving the basic problem but let's not be misleading. Also don't forget to call head.

In Haskell monads, you define a monadic type and then "bind" is the function that does something specific for that type. "It's a type" because Haskell uses static types and polymorphism to factor out common logic used by different functions. Of course Haskell list is a built-in type, but it's not magical except for the special bracket syntax. You can make a sugar-free user-defined type data List a = Nil | Cons a (Lis…

Yes, I know all of that. I wasn't saying it was magical, I was saying that in that particular code "amb expressed in terms of the List monad" is an accurate description, but "amb function" isn't really true. The monad is doing 100% of the ambiguous operation and the "amb function" does 0%.

As an analogy let's say I define "(" to do write to stdout, and "print" as id. Even though "print(4)" works as expected, my "print function" is a lie.

Or in C source code where adjacent strings get merged, I could [#define CONCAT ] so that ["ab" CONCAT "cd"] gets preprocessed to ["ab" "cd"] and parsed as ["abcd"]. But I didn't actually write a concatenation operator. The concatenation happens because of something else, it would happen even if you didn't use CONCAT, and you can sprinkle CONCAT all over your source code with no effect.

Re: McCarthy's Ambiguous Operator (2005)

#38

Post by billsix »

hopler wrote: post #32
billsix wrote: post #28

Earlier quoted context omitted.

Continuations also allowed me to implement python’s yield/send in 16 lines of Scheme code :-) http://billsix.github.io/bug.html#_make_generator

You can also implement scheme's call/cc with python's yield/send, right?

Incorrect. In c terms, you can think of callcc as a procedure which memcpy s the stack onto the heap for later application. And when it is later applied, the heap allocated stack is memcpy ed back into the stack region of memory, destroying the current stack.

Python and c#’s yield are nothing like that. It’s just syntactic sugar for iterators.

Re: McCarthy's Ambiguous Operator (2005)

#39

Post by dragonwriter »

billsix wrote: post #38
hopler wrote: post #32

Earlier quoted context omitted.

You can also implement scheme's call/cc with python's yield/send, right?

Incorrect. In c terms, you can think of callcc as a procedure which memcpy s the stack onto the heap for later application. And when it is later applied, the heap allocated stack is memcpy ed back into the stack region of memory, destroying the current stack. Python and c#’s yield are nothing like that. It’s just syntactic sugar for iterators.

Python yield actually supports coroutines with bidirectional communication, not just unidirectional iterators; while not as full featured as callcc, these cover quite a lot of the use cases.

Re: McCarthy's Ambiguous Operator (2005)

#40

Post by billsix »

dragonwriter wrote: post #39
billsix wrote: post #38

Earlier quoted context omitted.

Incorrect. In c terms, you can think of callcc as a procedure which memcpy s the stack onto the heap for later application. And when it is later applied, the heap allocated stack is memcpy ed back into the stack region of memory, destroying the current stack. Python and c#’s yield are nothing like that. It’s just syntactic sugar for iterators.

Python yield actually supports coroutines with bidirectional communication, not just unidirectional iterators; while not as full featured as callcc, these cover quite a lot of the use cases.

Agreed regarding use cases. My scheme implementation does both yield and send, cleanly imho, because of call/cc.
Post reply on HN