Hacker News Reader

Comment by bsaul | Hacker News Reader

side question : i remember a course in my logic class where our teacher showed us a programming language made of only two letters, and where all operations, numbers, etc were all defined with just those two letters. It was created by some famous logician but i can't find anything on the web about it.

Anyone here knows what that could be ?

edit : i think the lesson was showing curry's work on combinator logic..

View on HN

Sounds like SKI combinators. Three combinators: S,K and I. I is technically optional.

https://en.m.wikipedia.org/wiki/SKI_combinator_calculus

I would guess the SK combinators.

https://en.wikipedia.org/wiki/SKI_combinator_calculus

Thanks, that was the one. This looks like a more fundamental axiomatic than lisp meta-circular evaluator. I'm surprised it didn't give birth to more experimentation (maybe because i remember it had some very weird properties and things that looked a lot like inconsistencies..)

"very weird properties and things that looked a lot like inconsistencies"

Any idea what they were - as my final year project of my CS degree I did an implementation of a simple purely functional programming language that macro expanded into lambda calculus and then was converted into various sets of combinators for evaluation (from SK upwards). I thought there was actually a stunning lack of weirdness and inconsistency - mind you this did also come with a stunning lack of performance!

NB The trickiest bit of the whole project was writing a garbage collector so I could actually get these things to run on a shared Unix mini-computer....

Edit: Getting Y (and therefore recursion) working purely in terms of SK still amazes me.

I think to remember something about being able to compute the fixed point of the function x -> x+1 (that is, a number for which this function returns the same number). Our teacher showed us this function, and i think he also told us, curry reaction when people showed him this was something along the line of « well, that just means my theory is more powerful than yours, because it can express things yours can’t ».

that was 20 years ago, but it made a big impression on me, so i think my memories are correct :)

Probably it was indeed combinatory logic, but see also https://en.wikipedia.org/wiki/Iota_and_Jot

'0' and '1'? Sorry :P

You can technically do it with only one character (via Godel numbering and unary), but it gets annoying fast for obvious reasons.

The language Whitespace [1] has 3 characters only: spaces, tabs and linefeeds.

[1] https://en.wikipedia.org/wiki/Whitespace_(programming_langua...

Perhaps this is related. I learned that in fact you do not need for "God made the integers". The definition of every object in mathematics can be bootstrapped from the empty set. 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".

> 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".

This is not the usual von Neumann encoding (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...), so I think you may have started one level too encoded. The usual encoding puts 0 equal to the empty set, and n + 1 equal to the union of n (a set with n elements) and {n} (a singleton with 1 element).

In other words, if I understand the meaning of 'Etc.', your encoding puts

    0 = {Ø}, 1 = {0, Ø} = {{Ø}, Ø}, 2 = {1, Ø} = {{{Ø}, Ø}, Ø}, …,

whereas the usual encoding puts

    0 = Ø, 1 = 0 ∪ {0} = {Ø}, 2 = 1 ∪ {1} = {Ø, {Ø}}, ….

One advantage of this latter encoding is that the set n has n elements, and that the set n is n-times nested, in the sense that longest chain of elements x ∈ y ∈ z ∈ … ∈ n has length n. It also generalises nicely to ordinals (a transfinite generalization of the natural numbers), as explained in the above link (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...).

https://en.wikipedia.org/wiki/SK_combinator_calculus ?

Reply on news.ycombinator.com