WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
WolframOne
Mathematica
WolframAlpha Notebook Edition
Finance Platform
System Modeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Application Server
Enterprise Mathematica
WolframAlpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
WolframAlpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
WolframAlpha
WolframAlpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
WolframAlpha for Mobile
WolframAlphaPowered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledgebased programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technologyenabling science of the computational universe.
Wolfram Notebooks
The preeminent environment for any technical workflows.
Wolfram Engine
Software engine implementing the Wolfram Language.
Wolfram Natural Language Understanding System
Knowledgebased broadly deployed natural language.
Wolfram Data Framework
Semantic framework for realworld data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering WolframAlpha.
All Technologies »
Solutions
Engineering, R&D
Aerospace & Defense
Chemical Engineering
Control Systems
Electrical Engineering
Image Processing
Industrial Engineering
Mechanical Engineering
Operations Research
More...
Finance, Statistics & Business Analysis
Actuarial Sciences
Bioinformatics
Data Science
Econometrics
Financial Risk Management
Statistics
More...
Education
All Solutions for Education
Trends
Machine Learning
Multiparadigm Data Science
Internet of Things
HighPerformance Computing
Hackathons
Software & Web
Software Development
Authoring & Publishing
Interface Development
Web Development
Sciences
Astronomy
Biology
Chemistry
More...
All Solutions »
Learning & Support
Learning
Wolfram Language Documentation
Fast Introduction for Programmers
Wolfram U
Videos & Screencasts
Wolfram Language Introductory Book
Webinars & Training
Summer Programs
Books
Need Help?
Support FAQ
Wolfram Community
Contact Support
Premium Support
Paid Project Support
Technical Consulting
All Learning & Support »
Company
About
Company Background
Wolfram Blog
Events
Contact Us
Work with Us
Careers at Wolfram
Internships
Other Wolfram Language Jobs
Initiatives
Wolfram Foundation
MathWorld
ComputerBased Math
A New Kind of Science
Wolfram Technology for Hackathons
Student Ambassador Program
Wolfram for Startups
Demonstrations Project
Wolfram Innovator Awards
Wolfram + Raspberry Pi
Summer Programs
More...
All Company »
Search
WOLFRAM COMMUNITY
Connect with users of Wolfram technologies to learn, solve problems and share ideas
Join
Sign In
Dashboard
Groups
People
Message Boards
Answer
(
Unmark
)
Mark as an Answer
GROUPS:
Computer Science
Mathematics
Wolfram Language
Wolfram High School Summer Camp
4
Eric Paul
[WSC20] Analyzing and Computing with Combinators
Eric Paul
Posted
1 year ago
1408 Views

0 Replies

4 Total Likes
Follow this post

Introduction
The overall goal of this project is to explore computing with combinators and to analyze the completeness of combinatory bases.
Computing with Combinators
Introduction
Combinators can be thought of as higher order functions. They take in other combinators as arguments and return another combinator. The combinators S and K are a common basis that form a simple Turingcomplete language.
The reduction rules for S and K combinators:
I
n
[
]
:
=
S
K
B
a
s
i
s
=
k
[
x
_
]
[
y
_
]
x
,
s
[
x
_
]
[
y
_
]
[
z
_
]
x
[
z
]
[
y
[
z
]
]
;
S
K
B
a
s
i
s
/
/
C
o
l
u
m
n
O
u
t
[
]
=
k
[
x
_
]
[
y
_
]
x
s
[
x
_
]
[
y
_
]
[
z
_
]
x
[
z
]
[
y
[
z
]
]
A program is represented by the initial state of the combinator and computation is the act of applying all reductions until nothing more can be reduced (this process does not always terminate).
The goal here is to find out how to compute interesting things using combinators.
R
e
d
u
c
i
n
g
C
o
m
b
i
n
a
t
o
r
s
L
a
m
b
d
a
C
a
l
c
u
l
u
s
L
a
m
b
d
a
T
o
S
K
C
o
m
b
i
n
a
t
o
r
s
C
h
u
r
c
h
E
n
c
o
d
i
n
g
F
a
c
t
o
r
i
a
l
F
u
n
c
t
i
o
n
T
w
o
T
a
g
S
y
s
t
e
m
S
i
m
u
l
a
t
i
o
n
Analyzing Combinatory Bases
A combinatory basis is the set of primitive combinators used to build other combinators. So far we have seen S and K as the basis because it is simple and is Turingcomplete.
The goal here is to create a function that classifies a given basis as being complete or incomplete. A complete basis can recreate all other combinators and is Turingcomplete. An incomplete basis will not be able to do this.
C
o
m
b
i
n
a
t
o
r
E
q
u
a
l
i
t
y
E
n
u
m
e
r
a
t
i
n
g
C
o
m
b
i
n
a
t
o
r
s
C
h
a
n
g
e
o
f
C
o
m
b
i
n
a
t
o
r
B
a
s
i
s
C
l
a
s
s
i
f
y
C
o
m
b
i
n
a
t
o
r
s
G
e
n
e
r
a
t
e
R
a
n
d
o
m
C
o
m
b
i
n
a
t
o
r
s
F
i
n
d
B
u
i
l
d
a
b
l
e
C
l
a
s
s
e
s
C
h
e
c
k
f
o
r
I
n
c
o
m
p
l
e
t
e
n
e
s
s
Conclusion
For computing with combinators, I created a framework for creating programs for SK combinators. First the program is written at a higher level using the Church encoding. Then the program can be converted directly to SK combinators or first reduced at the lambda calculus level and then converted to SK combinators.
For analyzing combinatory bases, I created a function that attempts to find out whether or not a combinatory basis is complete. It first tries to use experimentally found rules to check if a given basis is able to create combinators of all necessary classes. It then tries to create an equivalent combinator in the given basis for both the S and K combinators.
Further Work
Much of the code in computing combinators is not very efficient. It works for reasonably sized combinators, but combinators that compute interesting things are rarely reasonably sized.
It would also be much better if what classes could be built from other classes was proven and not found experimentally as I could be missing combinations that never came up randomly.
Keywords
◼
Combinators
◼
Combinatory basis
POSTED BY:
Eric Paul
Answer
Mark as an Answer
Reply

Flag
Reply to this discussion
in reply to
Add Notebook
Community posts can be styled and formatted using the
Markdown syntax
.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Publish anyway
Cancel
Reply Preview
Attachments
Remove
Add a file to this post
Follow this discussion
or
Discard
Group Abstract
Be respectful. Review our
Community Guidelines
to understand your role and responsibilities.
Community Terms of Use
Feedback
Enable JavaScript to interact with content and submit forms on Wolfram websites.
Learn how »